以前遇到过的模型突然攻击我，被偷袭了。

description

有一个全集 $\{1,2,3,\dots,n\}$，你需要选出 $m$ 个其非空子集，这些子集要互不相同，且 $1\sim n$ 在这些子集里的出现次数都是偶数。计数方案。

$n,m\leq 10^6$。

solution

偶数的这个限制比较诡异，注意到我们几乎可以任意选集合，有一个常见的想法（可我忘了）是随便选前 $m-1$ 个集合，使用最后一个集合调整奇偶性，方案数就是 $\dbinom{2^n-1}{m-1}$。

这样显然会算进去一些不合法的，用容斥减掉，设 $f(i)$ 表示 $m=i$ 的答案。不合法的方案有三类：

  1. 第 $i$ 个集合是空集，这样就说明前 $i-1$ 个已经是合法的方案了，方案数是 $f(i-1)$。

  2. 第 $i$ 个集合与之前的集合重复了。这时我们钦定这个重复的集合，剩下的 $i-2$ 个集合一定是合法的，方案数为 $f(i-2)\times (2^n-1-(i-2))$

然后因为每个方案都会被计算 $i$ 次，要把答案除以 $i$。

$$ f(i)=\dfrac{\dbinom{2^n-1}{m-1}-f(i-1)-f(i-2)\times(2^n-i+1)}{i} $$

那个组合数预处理下降幂就可以算了。

code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

namespace solve
{
    const int maxn = 1e6 + 10;
    const int mod = 1e8 + 7;
    typedef long long ll;

    ll qpow(ll a, ll x, ll p)
    {
        ll res = 1;
        for (; x; x >>= 1, a = a * a % p)
            if (x & 1)
                res = res * a % p;
        return res;
    }
    ll fac[maxn], ifac[maxn], mi[maxn];
    ll down[maxn];
    int n;

    void init(int n = 1e6)
    {
        fac[0] = 1;
        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i % mod;
        ifac[n] = qpow(fac[n], mod - 2, mod);
        for (int i = n - 1; i >= 0; i--)
            ifac[i] = ifac[i + 1] * (i + 1) % mod;
    }
    int m;

    ll f[maxn];

    void main()
    {
        init();
        cin >> n >> m;
        ll x = qpow(2, n, mod) - 1;
        down[0] = 1;
        down[1] = x;
        for (int i = 2; i <= m; i++)
            down[i] = down[i - 1] * (down[1] - i + 1 + mod) % mod;
        f[0] = 1, f[1] = 0;
        for (int i = 2; i <= m; i++)
            f[i] = qpow(i, mod - 2, mod) * (down[i - 1] * ifac[i - 1] % mod - f[i - 1] - f[i - 2] * (qpow(2, n, mod) - 1 - (i - 2)) % mod) % mod;
        cout << (f[m] + mod) % mod << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve::main();
}