Link https://codeforces.com/problemset/problem/1279/D
普及题, 开个桶记录一下每个数出现的次数即可.
- #include<cstdio>
- #include<cctype>
- #include<vector>
- namespace IO
- {
- char ibuf[(1<<21)+1],*iS,*iT;
- char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
- int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
- }
- using IO::read;
- const int N=1000007,P=998244353;
- std::vector<int>a[N];
- int k[N],cnt[N];
- void mod(int&x){x-=P,x+=(x>>31&P);}
- int pow(int a,int k){int r=1;for(;k;k>>=1,a=1ll*a*a%P)if(k&1)r=1ll*a*r%P;return r;}
- int inv(int a){return pow(a,P-2);}
- int main()
- {
- int n=read(),in=inv(n),ans=0;
- for(int i=1,j,x;i<=n;++i) for(j=1,k[i]=read();j<=k[i];++j) ++cnt[x=read()],a[i].push_back(x);
- for(int i=1;i<=n;++i)
- {
- int sum=0;
- for(int x:a[i]) mod(sum+=1ll*cnt[x]*in%P);
- mod(ans+=1ll*sum*inv(k[i])%P);
- }
- printf("%d",1ll*ans*in%P);
- }
来源: http://www.bubuko.com/infodetail-3400006.html