【省选模拟】Comet OJ - Contest #16 小 C 的奇妙序列（DP）（组合意义）（拆分数）

本文主要是介绍【省选模拟】Comet OJ - Contest #16 小 C 的奇妙序列（DP）（组合意义）（拆分数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

先说一下 $k = 2$ 怎么做，要求 $E(a_i^2)=E(\sum (a_i+a_j)^2)=2\sum E(a_i^2)+2(\sum a_i)^2$
所以要维护 $(\sum a_i)^2$ ， $(\sum a_i+t)^2=(\sum a_i)^2+2t\sum a_i+t^2$ ，注意 $E(t\sum a_i)\neq E(t)*E(\sum a_i)$ ，而 $E(t\sum a_i)=E(\frac{2}{n}(\sum a_i)^2)$ ，所以就可以递推了
考虑这个的组合意义，就是每个点向前面随 $k$ 条带标号可重复的边，在原点有 $k$ 个带标号小球，问每一种 $d a g$ 小球全部走到终点的方案数（一条边可以有多个球），最后除以总方案就可以。
我们考虑把这个方案数 $d p$ 出来，一条边有多个球，而我们不需要关注是什么球，于是状态数是一个拆分数，然后分两步转移，第一步把 $i$ 的球分组引出去，第二步把外面的球匀一些到 $i + 1$ ，转移系数可以预处理出来

#include<bits/stdc++.h>
#define cs const
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pi;
cs int N = 1e5 + 50;
cs int M = 305;
cs int Mod = 998244353;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int mul(int a, int b){ return 1ll * a * b % Mod; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
int ksm(int a, int b){ int as=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) as=mul(as,a); return as; }
void Add(int &a, int b){ a = add(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
void Dec(int &a, int b){ a = dec(a, b); }
int n, K, tot;
int fac[11],ifac[11],C[11][11];
map<pair<int, vector<int> >, int> idx;
void pre_work(int n){fac[0]=fac[1]=ifac[0]=ifac[1]=1;for(int i=2; i<=n; i++) fac[i]=mul(fac[i-1],i);ifac[n]=ksm(fac[n],Mod-2);for(int i=n-1; i>=2; i--) ifac[i]=mul(ifac[i+1],i+1);for(int i=0; i<=n; i++) C[i][0]=1;for(int i=1; i<=n; i++)for(int j=1; j<=i; j++) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
vector<int> now;
vector<vector<int> > S[11];
void dfs(int c, int res, int mn){if(!res){idx[mp(c,now)]=++tot;S[c].pb(now); return;}for(int i=mn; i<=res; i++) now.pb(i), dfs(c, res-i, i), now.pop_back();
}
vector<pi> G1[N];
vector<pair<pi, int> > G2[N];
void sub_work(int c, vector<int> in, vector<int> out){static int c1[11], c2[11];vector<int> al(0,0);for(int i=0; i<=K; i++) c1[i]=c2[i]=0;int cf=mul(fac[K],ifac[K-out.size()]), cg=fac[K-c];for(auto t : out) ++c2[t], Mul(cg, ifac[t]), al.pb(t);for(auto t : in) ++c1[t], al.pb(t);for(int i=1; i<=K; i++) Mul(cf, C[c1[i]+c2[i]][c1[i]]), Mul(cg, ifac[c2[i]]);sort(al.begin(), al.end());int u = idx[mp(c,in)], v = idx[mp(K,al)];G1[u].pb(mp(v,cg)); G2[v].pb(mp(mp(u,cf),K-out.size()));
}
void work_trans(){for(int i=0; i<=K; i++) dfs(i,i,1);for(int i=0; i<=K; i++) for(auto x : S[i]) for(auto y : S[K-i]) sub_work(i, x, y);
}
int f[M], g[M], pw[11];
void work_f(){for(int i=1; i<=tot; i++) if(f[i])for(auto t : G1[i]) Add(g[t.fi],mul(f[i],t.se));for(int i=1; i<=tot; i++) f[i]=0;
}
void work_g(){for(int i=1; i<=tot; i++) if(g[i])for(auto t : G2[i]) Add(f[t.fi.fi],mul(g[i],mul(t.fi.se,pw[t.se])));for(int i=1; i<=tot; i++) g[i]=0;
}
void work(){ f[1] = 1; int iv = 1;for(int i=1; i<=n; i++){pw[0]=1; for(int j=1; j<=K; j++) pw[j]=mul(pw[j-1],i);work_f(); work_g(); Mul(iv,i); } cout << mul(ksm(ksm(iv,Mod-2),K),f[1]); 
}
int main(){scanf("%d%d",&n,&K); pre_work(10);work_trans(); work(); return 0;
}