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

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

​​传送门​​

#include#define cs const#define mp make_pair#define pb push_back#define fi first#define se secondusing namespace std;typedef pair 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 >, 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 now;vector > 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 G1[N];vector > G2[N];void sub_work(int c, vector in, vector out){ static int c1[11], c2[11]; vector 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。