题目传送门(BZOJ)

题解 :

今天靠这道题救了我垫底的命 233
我们先令求出的答案是有序的, 那么最后除以一个 M! 也就是乘一个 M!^{-1}\mod 19961993 即可
设状态 F[i] 为在长度为 i 时合法的有序方案数
长度为 i 时的总方案数量是 A_{2^n-1}^{i-1} 个,
之所以是 i-1 是因为当前 i-1 个确定了时, 为了满足出现偶数次的条件, 第 i 个也随之确定了.
然后开始斥掉不合法的方案
首先, 若前 i-1 个已经合法, 那么第 i 个只能是空集, 这是不合法的, 所以要减掉 F[i-1]
然后当第 i 个和前面某一个重复的时候, 也不合法
前面共有 i-1 个位置, 我们先把 i-1 这个系数放在这里, 考虑对于单个位置有多少个会和第 i 个位置重复的
首先我们要求这前 i-1 个, 去掉这个重复的 x 一定是合法的
原因是因为加上了 i 合法, 那么对于 ix 因为重复所以若某位有音阶就一定有两个, 减去偶数个仍合法
那么就是 F[i-2] 种合法的方案了.
F[i-2] 种合法的方案里, 这个位置还可以有 (2^n-1)-(i-2) 种取值(把另外 i-2 个已经取得去掉)
\therefore F[i] = A_{2^n-1}^{i-1} – (F[i-1] + (i-1)\times F[i-2]\times (2^n-1)-(i-2))
我们 O(N) 递推出 F[M], 然后乘一个 M! 的逆元即可

代码 :

#include <cstdio>#define ll long longconst int p = 1e8+7;inline ll qp(ll x, int y) { ll res = 1; for(; y; y >>= 1, x = (ll)x*x%p) if(y&1) res = (ll)res*x%p; return res;}ll A[1000010], f[1000010];int main() { int n, m; scanf("%d%d", &n, &m); int tmp = qp(2, n)-1; if(tmp < 0) tmp += p; A[0] = 1; for(int i = 1; i <= m; i ++ ) A[i] = (A[i-1]*(((ll)tmp-i+1+p)%p))%p; for(int i = 3; i <= m; i ++ ) f[i] = (A[i-1]-f[i-1]-(f[i-2]*(i-1)%p*(tmp-i+2)%p)+p)%p; ll fac = 1; for(int i = 2; i <= m; i ++ ) fac = fac*i%p; f[m] = f[m]*qp(fac, p-2)%p; printf("%lld\n", (f[m]+p)%p);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<