【题解】相互再归的鹅妈妈 容斥 YZOJ50120 — Iris

同步发表于 博客园

题目大意

给出一个二进制数 $R$，在 $[0, R-1]$ 中选 $n$ 个互不相同数，问异或和为 $0$ 的方案数。

$|R|\le 10^6,n\le 7$.

解题思路

因为限制 $n$ 个数互不相同难以实现，所以考虑允许相同怎么求方案数，然后容斥做。

记可以相同的 $n$ 个数异或和为 $0$ 的方案数为 $h(n)$，先考虑怎么容斥，不妨用连边表示两个数不能相同，那么就枚举被违反的限制，令被枚举的边集为 $S$，把被钦定相同的数缩点，那么答案就是：

$$
\sum_{S}(-1)^{|S|}h(\text{奇数点连通块数目})\cdot R^{\text{偶数点连通块数目}}
$$

虽然这个部分可以以 $O(2^{\frac{n(n-1)}{2}})$ 的复杂度通过，但是还是考虑稍微快一点的 $O(\operatorname{Bell}(n))$ 的复杂度怎么做。

试着写多项式复杂度的做法然而只搞出了五次方的东西 T^T

直接枚举每个连通块中是哪些点，然后考虑所有使得连出来的连通块是这个结果的边集的 $\sum(-1)^{|S|}$ 是多少。

不难发现每个连通块其实是相互独立的，所以可以直接算出使得单个连通块连通的边集的 $\sum(-1)^{|S|}$，然后乘起来。

因为在用连边表示两个数不能相同时，得到的是完全图，所以单个连通块的 $\sum(-1)^{|S|}$ 之和连通块包含的点数有关，不妨记为 $f(n)$。

可以用斯特林反演直接推得 $f(n)=(-1)^{n-1}(n-1)!$，但是也可以二项式反演来得出。

令 $g(n)$ 表示 $n$ 个点不要求连通的 $\sum(-1)^{|S|}$，那么 $g$ 的值其实就是 $g(n)=[n=1]$，然后是个经典容斥：
$$
f(n)=g(n)-\sum_{i=1}^n\binom{n-1}{i-1}\cdot f(i)\cdot g(n-i)
$$
那么现在就只要考虑 $h(n)$ 怎么求了，比较暴力 (要求所有 $1\sim n$ 的方案数，所以应该是 $O(n^4|R|)$ ? ) 的数位 dp 不难想，就直接求第几位，有几个数还没有脱离边界的方案数。然而这个做法的空间复杂度 $O(n^2|R|)$ ，无法通过。

考虑一个更巧的思路，考虑第一个脱离边界的数是从哪一位开始脱离，那么在这一位之后，只要拿出一个脱离边界的数做收尾工作，其他的数可以随便填，从这个角度去考虑，就可以得到时间复杂度 $O(n|R|)$ 的做法了。

代码

void check(int m){
    int sum = 1, siz[2]{};
    lfor(i, 1, m) sum = 1ll * sum * f[cnt[i]] % mod, ++siz[cnt[i] & 1];
    sum = 1ll * sum * qpow(suf[mk], siz[0]) % mod;
    sum = 1ll * sum * h[siz[1]] % mod;
    MOD(Ans += sum - mod);
}
void Dfs(int x, int idcnt){
    if(x > n) return check(idcnt);
    lfor(i, 1, idcnt) ++cnt[i], Dfs(x + 1, idcnt), --cnt[i];
    ++cnt[idcnt + 1], Dfs(x + 1, idcnt + 1), --cnt[idcnt + 1];
}

signed main(){
    read(n), read(k), prep(n), pw[0] = 1;
    scanf("%s", s + 1), m = strlen(s + 1), mk = m * k;
    lfor(i, 1, m) s[i] -= '0';
    lfor(i, 0, k - 1) lfor(j, 1, m) s[i * m + j] = s[j];
    reverse(s + 1, s + mk + 1);
    lfor(i, 1, mk){
        pw[i] = 2ll * pw[i - 1] % mod;
        MOD(suf[i] = suf[i - 1] + s[i] * pw[i - 1] % mod - mod);
    }   

    bool have_one = 0; h[0] = 1;
    rfor(i, mk, 1) if(s[i]){
        memset(dp, 0, sizeof dp), dp[0][0][0] = 1;
        lfor(j, 1, n){
            lfor(a, 0, 1) lfor(b, 0, 1){
                MOD(dp[j][1][b] += 1ll * dp[j - 1][a][b] * (a ? pw[i - 1] : 1) % mod - mod);
                MOD(dp[j][a][b ^ 1] += 1ll * dp[j - 1][a][b] * suf[i - 1] % mod - mod);
            }
            if(j % 2 == 0 || have_one == 0) MOD(h[j] += dp[j][1][0] - mod);
        }
        have_one |= s[i];
    }

    f[1] = g[1] = 1;
    lfor(i, 1, n) lfor(j, 1, i - 1)
        MOD(f[i] -= 1ll * C(i - 1, j - 1) * f[j] % mod * g[i - j] % mod);

    Dfs(1, 0);

    cout << 1ll * Ans * ifac[n] % mod << endl;
    return 0;
}