*AtCoder Regular Contest 096E

$n \leq 3000$个酱，丢进拉面里，需要没两碗面的酱一样，并且每个酱至少出现两次，面的数量随意。问方案数。对一给定质数取模。

没法dp就大力容斥辣。。

$Ans=\sum_{i=0}^n (-1)^i \binom{n}{i} f(i)$

其中$f(i)$是：$i$个酱不符合题意（就是没出现或出现一次），而其他酱随意的方案数。

然后先考虑$i$个坏酱：$g(i,j)$--$i$个坏酱，放$j$碗面里方案，因为$j$最多为$i$，然后酱是可以出现一次或不出现的。这是一个斯二林改，$g(i,j)=g(i-1,j-1)+g(i-1,j)*(j+1)$，$j+1$的$1$就是可以不丢进去。

然后考虑自由酱。$h(i,j)$--$g(i,j)$的基础上再考虑$n-i$个自由酱，$h(i,j)=g(i,j)2^{2^{n-i}}2^{(n-i)j}$，$2^{2^{n-i}}$是指这$j$碗面之外的情况，就好像只有这$n-i$个酱然后胡乱放；$2^{(n-i)j}$就是这$j$碗面的其他酱随便放，每碗面有$2^{n-i}$种选择。

然后$f(i)=\sum h(i,j)$，就没了。

巴特西

*AtCoder Regular Contest 096E - Everything on It

最新文章

热门文章