php做自己的网站,建设德育网站的意义,dw怎么做网站,承德网站制作公司优选网十科技https://atcoder.jp/contests/abc321/tasks/abc321_g
这种题都没看出来我要去退役了
看完题目#xff0c;可以获得#xff1a;
期望、连通块#xff1a;显然拆贡献啊#xff01; n ≤ 17 n\le 17 n≤17#xff1a;这不明显状压#xff1f;结合前面连通块#xff0c;就…https://atcoder.jp/contests/abc321/tasks/abc321_g
这种题都没看出来我要去退役了
看完题目可以获得
期望、连通块显然拆贡献啊 n ≤ 17 n\le 17 n≤17这不明显状压结合前面连通块就是枚举连通块啊继续分析第2点17这么小显然枚举子集。为啥枚举计数题只有容斥这个套路啊
然后就很裸了。
为啥容斥因为拆完贡献后要使得恰好为一个连通块。
这里还有个小套路。容斥是为了不重不漏我们可以枚举最编号小点所在的单个连通块。剩下随便连。 nread(); mread(); init(m); for(i1; im; i) kread(), R[1k-1]; for(i1; im; i) kread(), B[1k-1]; for(s1; s(1n); s) {for(i1; in; i) if(s(1i-1)) break; R[s]R[s-(1i-1)]R[1i-1]; B[s]B[s-(1i-1)]B[1i-1]; if(R[s]B[s]) {f[s]g[s]fac[R[s]]; for(t(s-1)s; t; t(t-1)s) if(t(1i-1)) Add(g[s], -g[t]*f[s-t]); Add(ans, g[s]*fac[m-R[s]]); }}ans(ans*ifac[m]%momo)%mo; printf(%lld, ans);
