CF1228E Another Filling the Grid

题目链接

问题分析

比较显见的容斥，新颖之处在于需要把横竖一起考虑……

可以枚举没有\(1\)的行数和列数，答案就是
\[\sum\limits_{i=0}^n\sum\limits_{j=0}^m(-1)^{i+j}{n\choose i}{n \choose j}(k-1)^{i*n+j*n-i*j}k^{n*n-i*n-j*n+i*j}\]
个数算对就好了……

参考程序

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

const LL Mod = 1000000007;
const LL Maxn = 260;
LL n, k;
LL Fact[ Maxn ], INV[ Maxn ];

LL Pow( LL x, LL y ) {
    LL Ans = 1;
    for( ; y; y >>= 1, x = x * x % Mod )
        if( y & 1 )
            Ans = Ans * x % Mod;
    return Ans;
}

LL C( LL n, LL m ) {
    return Fact[ n ] * INV[ m ] % Mod * INV[ n - m ] % Mod;
}

int main() {
    Fact[ 0 ] = 1;
    for( LL i = 1; i < Maxn; ++i ) Fact[ i ] = Fact[ i - 1 ] * i % Mod;
    INV[ Maxn - 1 ] = Pow( Fact[ Maxn - 1 ], Mod - 2 );
    for( LL i = Maxn - 2; i >= 0; --i ) INV[ i ] = INV[ i + 1 ] * ( i + 1 ) % Mod;

    scanf( "%lld%lld", &n, &k );
    LL Ans = 0;
    for( LL i = 0; i <= n; ++i )
        for( LL j = 0; j <= n; ++j ) {
            LL Num = ( i + j ) * n - i * j;
            LL t1 = C( n, i ) * C( n, j ) % Mod;
            LL Method = t1 * Pow( k - 1, Num ) % Mod * Pow( k, n * n - Num ) % Mod;
            if( ( i + j ) % 2 == 0 ) Ans = ( Ans + Method ) % Mod;
            else Ans = ( Ans + Mod - Method ) % Mod;
        }
    printf( "%lld\n", Ans );
    return 0;
}