题目大意：求一个 有标号树的 本质不同的 有根点分树 数量。要求平方。
思考：咕咕咕
1 #include<bits/stdc++.h> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long int ll; 5 const int maxn=5E3+5; 6 int n; 7 int size,head[maxn]; 8 ll f[maxn][maxn],C[maxn][maxn]; 9 struct edge 10 { 11 int to,next; 12 }E[maxn*2]; 13 inline void add(int u,int v) 14 { 15 E[++size].to=v; 16 E[size].next=head[u]; 17 head[u]=size; 18 } 19 ll tmp[maxn]; 20 int sum[maxn]; 21 void dfs(int u,int F) 22 { 23 f[u][0]=1; 24 for(int e=head[u];e;e=E[e].next) 25 { 26 int v=E[e].to; 27 if(v==F) 28 continue; 29 dfs(v,u); 30 for(int i=0;i<=sum[u]+sum[v];++i) 31 tmp[i]=0; 32 for(int i=0;i<=sum[u];++i) 33 for(int j=0;j<=sum[v];++j) 34 tmp[i+j]=(tmp[i+j]+f[u][i]*f[v][j]%mod*C[i+j][i])%mod; 35 sum[u]+=sum[v]; 36 for(int i=0;i<=sum[u];++i) 37 f[u][i]=tmp[i]; 38 } 39 memset(tmp,0,sizeof(tmp)); 40 ++sum[u]; 41 for(int i=1;i<=sum[u];++i) 42 tmp[i]=f[u][i-1]; 43 for(int i=sum[u];i>=0;--i) 44 f[u][i]=(f[u][i+1]+tmp[i])%mod; 45 } 46 int main() 47 { 48 freopen("game.in","r",stdin); 49 freopen("game.out","w",stdout); 50 ios::sync_with_stdio(false); 51 cin>>n; 52 for(int i=2;i<=n;++i) 53 { 54 int x,y; 55 cin>>x>>y; 56 assert(x!=y); 57 add(x,y); 58 add(y,x); 59 } 60 for(int i=0;i<=n;++i) 61 { 62 C[i][0]=1; 63 for(int j=1;j<=i;++j) 64 C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 65 } 66 dfs(1,0); 67 cout<<f[1][0]<<endl; 68 return 0; 69 }
题目链接：https://www.luogu.com.cn/problem/P1393
题解：https://mivik.gitee.io/2020/solution/mivik-string-contest-title/
1 #include<bits/stdc++.h> 2 #define mod 998244353 3 #define G 3 4 #define Gi 332748118 5 using namespace std; 6 typedef long long int ll; 7 const int maxn=1E5+5; 8 ll n,m,k; 9 int a[maxn]; 10 inline ll qpow(ll x,ll y) 11 { 12 ll ans=1,base=x; 13 while(y) 14 { 15 if(y&1) 16 ans=ans*base%mod; 17 base=base*base%mod; 18 y>>=1; 19 } 20 return ans; 21 } 22 int fail[maxn]; 23 namespace POLY 24 { 25 vector<ll>pre[20],prei[20]; 26 inline void init() 27 { 28 for(int i=1;i<20;++i) 29 { 30 ll d=qpow(G,(mod-1)/(1<<i)); 31 for(ll j=0,w=1;j<(1<<i);++j,w=w*d%mod) 32 pre[i].push_back(w); 33 d=qpow(Gi,(mod-1)/(1<<i)); 34 for(ll j=0,w=1;j<(1<<i);++j,w=w*d%mod) 35 prei[i].push_back(w); 36 } 37 } 38 int r[(1<<20)+5]; 39 inline void DFT(ll*A,int limit) 40 { 41 for(int i=1;i<limit;++i) 42 if(i<r[i]) 43 swap(A[i],A[r[i]]); 44 for(int len=2,now=1;len<=limit;len<<=1,++now) 45 for(int i=0;i<limit;i+=len) 46 for(int j=0,p1=i,p2=i+len/2;j<len/2;++j,++p1,++p2) 47 { 48 ll a=A[p1],b=A[p2]*pre[now][j]%mod; 49 A[p1]=a+b>=mod?a+b-mod:a+b; 50 A[p2]=a-b<0?a-b+mod:a-b; 51 } 52 } 53 inline void IDFT(ll*A,int limit) 54 { 55 for(int i=1;i<limit;++i) 56 if(i<r[i]) 57 swap(A[i],A[r[i]]); 58 for(int len=2,now=1;len<=limit;len<<=1,++now) 59 for(int i=0;i<limit;i+=len) 60 for(int j=0,p1=i,p2=i+len/2;j<len/2;++j,++p1,++p2) 61 { 62 ll a=A[p1],b=A[p2]*prei[now][j]%mod; 63 A[p1]=a+b>=mod?a+b-mod:a+b; 64 A[p2]=a-b<0?a-b+mod:a-b; 65 } 66 } 67 ll tmp1[(1<<20)+5],tmp2[(1<<20)+5]; 68 inline void FFT(ll*A,ll*B,int n1,int n2,ll*to) 69 { 70 int limit=1; 71 while(limit<n1+n2+1) 72 limit<<=1; 73 for(int i=0;i<limit;++i) 74 tmp1[i]=tmp2[i]=0; 75 for(int i=0;i<=n1;++i) 76 tmp1[i]=A[i]; 77 for(int i=0;i<=n2;++i) 78 tmp2[i]=B[i]; 79 for(int i=0;i<limit;++i) 80 r[i]=(r[i>>1]>>1)|((i&1)?(limit>>1):0); 81 DFT(tmp1,limit); 82 DFT(tmp2,limit); 83 for(int i=0;i<limit;++i) 84 tmp1[i]=tmp1[i]*tmp2[i]%mod; 85 IDFT(tmp1,limit); 86 ll base=qpow(limit,mod-2); 87 for(int i=0;i<=n1+n2;++i) 88 to[i]=tmp1[i]*base%mod; 89 } 90 ll tmp3[(1<<20)+5],tmp4[(1<<20)+5],tmp5[(1<<20)+5]; 91 inline void inv(ll*A,int n) 92 { 93 tmp3[0]=qpow(A[0],mod-2); 94 for(int now=1;now<n+1;now<<=1) 95 { 96 int limit=now<<2; 97 for(int i=0;i<limit;++i) 98 tmp4[i]=tmp5[i]=0; 99 for(int i=0;i<now;++i) 100 tmp4[i]=tmp3[i]; 101 for(int i=0;i<(now<<1);++i) 102 tmp5[i]=A[i]; 103 for(int i=0;i<limit;++i) 104 r[i]=(r[i>>1]>>1)|((i&1)?(limit>>1):0); 105 DFT(tmp4,limit); 106 DFT(tmp5,limit); 107 for(int i=0;i<limit;++i) 108 tmp3[i]=((-tmp4[i]*tmp4[i]%mod*tmp5[i]%mod+tmp4[i]*2)%mod+mod)%mod; 109 IDFT(tmp3,limit); 110 ll base=qpow(limit,mod-2); 111 for(int i=0;i<(now<<1);++i) 112 tmp3[i]=tmp3[i]*base%mod; 113 } 114 for(int i=0;i<=n;++i) 115 A[i]=tmp3[i]; 116 } 117 } 118 ll C[maxn]; 119 inline void solve() 120 { 121 int pos=0; 122 for(int i=2;i<=k;++i) 123 { 124 while(pos&&a[i]!=a[pos+1]) 125 pos=fail[pos]; 126 if(a[i]==a[pos+1]) 127 ++pos; 128 fail[i]=pos; 129 } 130 for(int p=k;p;p=fail[p]) 131 C[k-p]=1; 132 for(int i=n;i>=1;--i) 133 C[i]=(C[i]-C[i-1]*m%mod+mod)%mod; 134 ++C[k]; 135 POLY::inv(C,n); 136 for(int i=n;i>=k;--i) 137 C[i]=C[i-k]; 138 ll ans=0; 139 for(int i=k;i<=n;++i) 140 ans=(ans+C[i]*qpow(m,n-i))%mod; 141 ans=(ans%mod+mod)%mod; 142 ans=ans*qpow(qpow(m,n),mod-2)%mod; 143 cout<<ans<<endl; 144 } 145 inline int read() 146 { 147 char ch=getchar(); 148 while(!isdigit(ch))ch=getchar(); 149 int s=ch-'0';ch=getchar(); 150 while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} 151 return s; 152 } 153 int main() 154 { 155 freopen("bye.in","r",stdin); 156 freopen("bye.out","w",stdout); 157 ios::sync_with_stdio(false); 158 POLY::init(); 159 n=read(),m=read(),k=read(); 160 for(int i=1;i<=k;++i) 161 a[i]=read(); 162 solve(); 163 return 0; 164 }