[CF1228E] Another Filling the Grid

[CF1228E] Another Filling the Grid - 容斥,组合

Description

给定一个n*n的矩阵，用1~k的数填充，每行每列最小值均为1，问有多少填法（mod1e9+7） (n le 250, k le 10^9)

Solution

至少有多少 i 行 j 列违反规定的方案数是好求的

具体地，先用两个组合数选出这 i 行 j 列，然后对于涉及到的这些格子，每个格子的选择是 k-1 种，其它是 k 种，怼两个幂上去即可

考虑容斥，那么 i 个行 j 个列的容斥系数就是 pow(-1,i+j)，枚举 i,j 计算即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

namespace math_mod
{
    int c__[5005][5005], fac__[1000005];

    int qpow(int p, int q)
    {
        return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
    }

    int inv(int p)
    {
        return qpow(p, mod - 2);
    }

    int fac(int p)
    {
        if (p <= 1000000)
            return fac__[p];
        if (p == 0)
            return 1;
        return p * fac(p - 1) % mod;
    }

    int __fac(int p)
    {
        return fac(p);
    }

    int ncr(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        return fac(n) * inv(fac(r)) % mod * inv(fac(n - r)) % mod;
    }

    void math_presolve()
    {
        fac__[0] = 1;
        for (int i = 1; i <= 1000000; i++)
        {
            fac__[i] = fac__[i - 1] * i % mod;
        }
        for (int i = 0; i <= 5000; i++)
        {
            c__[i][0] = c__[i][i] = 1;
            for (int j = 1; j < i; j++)
                c__[i][j] = c__[i - 1][j] + c__[i - 1][j - 1], c__[i][j] %= mod;
        }
    }

    int __c(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        if (n > 5000)
            return ncr(n, r);
        return c__[n][r];
    }
}

using namespace math_mod;

signed main()
{
    ios::sync_with_stdio(false);
    math_presolve();
    int n, k;
    cin >> n >> k;
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            int f = n * (i + j) - i * j;
            int tmp = __c(n, i) * __c(n, j) % mod * qpow(k - 1, f) % mod * qpow(k, n * n - f) % mod;
            if ((i + j) & 1)
                ans -= tmp;
            else
                ans += tmp;
            ans %= mod;
            ans += mod;
            ans %= mod;
        }
    }
    cout << ans << endl;
}