【AGC 005F】Many Easy Problems
Description
One day, Takahashi was given the following problem from Aoki:
You are given a tree with N vertices and an integer K. The vertices are numbered 1 through N. The edges are represented by pairs of integers （ai,bi）.
For a set S of vertices in the tree, let f(S) be the minimum number of the vertices in a subtree of the given tree that contains all vertices in S.
There are C(n,k) ways to choose K vertices from the trees. For each of them, let S be the set of the chosen vertices, and find the sum of f(S) over all C(n,k) ways.
Since the answer may be extremely large, print it modulo 924844033(prime).
Since it was too easy for him, he decided to solve this problem for all K=1,2...N.
2≤N≤200000，1≤ai,bi≤N.The given graph is a tree.
Input
Output
Print N lines. The i-th line should contain the answer to the problem where K=i, modulo 924844033.題意：給定一棵 $n$ 個節點的樹，選出 $k$ 個特殊點，假設點集為 $S$，令 $f(S)$ 為最小的包含這 $k$ 個節點的連通塊，分別求出 $k=1...n$ 在所有情況下的 $f(S)$ 的和。
分析：
考慮暴力，一個點被統計在連通塊內，即在以它為根時，選出來的 $k$ 個點都在它的同一個兒子的子樹內。即節點 $x$ 被統計進答案的次數 $g(x)$ 為：
$$g(x)=\binom{n}{k}-\sum _{(x,i)\subseteq E}\binom{sz_{i}}{k}$$
令 $cnt_{x}$ 表示上述公式里有多少個 $sz_{i}=x$，那么可以得到：
$$ans_{k}=\sum _{i=1}^{n}cnt_{i}\cdot\binom{i}{k}$$
整理可得：
$$k!\cdot ans_{k}=\sum _{i=1}^{n}\frac{cnt_{i}\cdot i!}{(i-k)!}$$
令 $a_{i}=cnt_{i}\cdot i!$，$b_{i}=(n-i)!$，則可得：
$$k!\cdot ans_{k}=\sum _{i=1}^{n}a_{i}\cdot b_{n-i+k}$$
最終答案為 $n\cdot \binom{n}{k}-ans_{k}$ 。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define LL long long 5 using namespace std; 6 const int N=2e5+5; 7 const int M=524288+5; 8 const int mod=924844033; 9 int n,nn,cnt,u,v,ans,first[N],fac[N],inv[N]; 10 int num[N],sz[N],a[M],b[M]; 11 struct edge{int to,next;}e[N*2]; 12 int read() 13 { 14 int x=0,f=1;char c=getchar(); 15 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 16 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 17 return x*f; 18 } 19 void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;} 20 void dfs(int x,int fa) 21 { 22 sz[x]=1; 23 for(int i=first[x];i;i=e[i].next) 24 { 25 int to=e[i].to; 26 if(to==fa)continue; 27 dfs(to,x); 28 sz[x]+=sz[to]; 29 } 30 if(fa!=-1)a[sz[x]]++,a[n-sz[x]]++; 31 } 32 int power(int a,int b) 33 { 34 int ans=1; 35 while(b) 36 { 37 if(b&1)ans=1ll*ans*a%mod; 38 a=1ll*a*a%mod;b>>=1; 39 } 40 return ans; 41 } 42 void ntt(int *a,int n,int f) 43 { 44 int k=0;while((1<<k)<n)k++; 45 for(int i=0;i<n;i++) 46 { 47 int t=0; 48 for(int j=0;j<k;j++) 49 if(i&(1<<j))t|=(1<<(k-j-1)); 50 if(i<t)swap(a[i],a[t]); 51 } 52 for(int l=2;l<=n;l<<=1) 53 { 54 int m=l>>1,nw=power(5,(mod-1)/l); 55 if(f==-1)nw=power(nw,mod-2); 56 for(int *p=a;p!=a+n;p+=l) 57 { 58 int w=1; 59 for(int i=0;i<m;i++) 60 { 61 int t=1ll*p[m+i]*w%mod; 62 p[m+i]=(p[i]-t+mod)%mod; 63 p[i]=(p[i]+t)%mod; 64 w=1ll*w*nw%mod; 65 } 66 } 67 } 68 if(f==-1) 69 { 70 int inv=power(n,mod-2); 71 for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod; 72 } 73 } 74 int main() 75 { 76 n=read(); 77 for(int i=1;i<n;i++) 78 { 79 u=read();v=read(); 80 ins(u,v);ins(v,u); 81 } 82 dfs(1,-1); 83 fac[0]=1; 84 for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod; 85 inv[n]=power(fac[n],mod-2); 86 for(int i=n;i>=1;i--)inv[i-1]=1ll*inv[i]*i%mod; 87 for(int i=1;i<=n;i++)a[i]=1ll*a[i]*fac[i]%mod; 88 for(int i=0;i<=n;i++)b[n-i]=inv[i]; 89 nn=1;while(nn<n+n+1)nn<<=1; 90 ntt(a,nn,1);ntt(b,nn,1); 91 for(int i=0;i<nn;i++)a[i]=1ll*a[i]*b[i]%mod; 92 ntt(a,nn,-1); 93 for(int i=1;i<=n;i++) 94 { 95 ans=1ll*fac[n]*inv[i]%mod*inv[n-i]%mod*n%mod; 96 printf("%lld\n",(ans-1ll*a[n+i]*inv[i]%mod+mod)%mod); 97 } 98 return 0; 99 }
浙公網安備 33010602011771號