jzoj5765 【省选模拟8.5】相互再归的鹅妈妈 （集合划分，斯特林反演）

$mk<=5e6，m<=5e4$

解法

先考虑可以有相同怎么做：
枚举一个第一个脱离限制的位置，然后用一个脱离限制的数来安排使得异或和为0，其他数可以任意取（要分是否脱离限制确定方案数）。这样可以计算出g(n)表示n个可以相同的数，异或和为0的答案。

斯特林反演式子：
$[n=1] = \sum_{m的集合划分A} ~~~~\prod(ai-1)! \cdot (-1)^{ai-1}$

证明非常简单，$\prod$右侧是圆周排列加上一个正负1的系数
等式右边也就是

$$\sum_k s(n,k) \cdot (-1) ^{n - k}$$ ，其中k是所划分的集合个数。
不难得出 $s(n) \cdot (-1) ^{n - k}$的生成函数就是 $x(x-1)(x-2)...(x-n+1)=x^{n下降}$
令x=1,那么等式右侧就是 $1^{n下降} = s(n,0) + 原式$，即 $原式= [n=1]$
我们要求的就是满足 $\prod [ai=1]的方案，$根据这个反演一波即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#define lowbit(x) ((x) & -(x))
using namespace std;
typedef long long ll;const ll mo = 1e9 + 7;
ll n, m, k, len;
char s[50100];
ll a[5000100],suf[5000100],mi[5000100];
ll f[8][2][2],g[8],ans,jc[8],mir[8];
ll q[8],size[8];
void dfs(ll x,ll c) {if (x > n) {memset(size,0,sizeof size);for (ll i = 1; i <= n; i++) size[q[i]]++;ll eve = 0, xs = 1;for (ll i = 1; i <= c; i++) {if (size[i] % 2 == 0) eve++;xs = xs * jc[size[i] - 1] % mo * ((size[i]-1)%2==0?1:-1) % mo;}ll odd = c - eve;(ans += xs * g[odd] % mo * mir[eve]) %= mo;return;}q[x] = c + 1;dfs(x + 1, c + 1);for (ll i = 1; i <= c; i++) {q[x] = i;dfs(x + 1, c);}
}
ll ksm(ll x,ll y) {ll ret = 1;for (; y; y>>=1) {if (y & 1) ret = ret * x % mo;x = x * x % mo;}return ret;
}
int main() {freopen("mothergoose.in","r",stdin);freopen("mothergoose.out","w",stdout);cin>>n>>k;jc[0] = 1;for (ll i = 1; i <= n; i++) jc[i] = jc[i - 1] * i;scanf("%s",s + 1); m = strlen(s + 1);for (ll i = 1; i <= k; i++) for (ll j = 1; j <= m; j++) {a[++len] = s[j] - '0';}ll w = 1; mi[len+1] = 1;for (ll i = len; i; i--, w = w * 2 % mo) {suf[i] = (suf[i+1] + w * a[i]) % mo;mi[i] = w * 2 % mo;}mir[0] = 1;for (ll i = 1; i <= n; i++) mir[i] = mir[i - 1] * suf[1] % mo;ll hasone = 0;for (ll i = 1; i <= len; i++) if (a[i] == 1) {memset(f,0,sizeof f);f[0][0][0] = 1;for (ll j = 1; j <= n; j++) {for (ll z = 0; z < 2; z++) //odd or evenfor (ll e = 0; e < 2; e++) { //has or not(f[j][z^1][e] += f[j-1][z][e] * suf[i+1]) %=mo;(f[j][z][1]   += f[j-1][z][e] * (e == 1 ? mi[i+1] : 1)) %= mo;}if (j%2==0 || !hasone) {(g[j] += f[j][0][1]) %= mo;}}hasone = 1;}g[0] = 1;dfs(1,0); ans = (ans + mo) % mo;cout<<ans * ksm(jc[n], mo - 2) % mo<<endl;
}