82: 模拟赛-校验码 容斥

$des$

$sol$

由于二进制的每一位都是独立的

所以将题意转化为

$n imes m$ 的矩形填入 $0/1$,使得每行每列都至少有一个$1$ 的方案数

考虑对行进行容斥

Answer = 全部的(每列至少一黑) - 有一行全白（每列至少一黑）+ 有两行全白（每列至少一黑） + cdots

即 $$Answer = sum_{k = 0} ^ {n} (-1) ^ k (2 ^ {n - k} - 1) ^ m$$

这样求出的答案的位数次方就是此题的答案

$code$

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

#define LL long long
#define Rep(i, a, b) for(LL i = a; i <= b; i ++)

const int N = 60;
const LL Mod = 1e9 + 7;

LL n, m, k_;

namespace $ {
    LL fac[N], ifac[N];
    LL Ksm(LL a, LL b) {
        LL ret = 1;
        while(b) {
            if(b & 1) ret = ret * a % Mod;
            a = a * a % Mod;
            b >>= 1;
        }
        return ret;
    }
    void Per() {
        fac[0] = 1;
        Rep(i, 1, 55) fac[i] = fac[i - 1] * i % Mod;
        ifac[55] = Ksm(fac[55], Mod - 2);
        for(int i = 55; i >= 1; i --) ifac[i - 1] = ifac[i] * i % Mod;
    }
    LL C(LL x, LL y) {
        return fac[x] * ifac[y] % Mod * ifac[x - y] % Mod;
    }
    
    LL Calc() {
        LL ans = 0;
        Rep(k, 0, n) {
            if(k % 2 == 0)ans = (ans + C(n, k) * Ksm((Ksm(2, n - k) - 1 + Mod) % Mod, m)) % Mod;
            else ans = (ans - C(n, k) * Ksm((Ksm(2, n - k) - 1 + Mod) % Mod, m) % Mod + Mod) % Mod;
        }
        return Ksm(ans, k_);
    }
}

int main() {
    $:: Per();
    int t;
    cin >> t;
    Rep(tt, 1, t) {
        cin >> n >> m >> k_;
        cout << $:: Calc() << '
';    
    }
    return 0;    
}