链接:

https://codeforces.com/contest/1228/problem/E

题意:

You have n×n square grid and an integer k. Put an integer in each cell while satisfying the conditions below.

All numbers in the grid should be between 1 and k inclusive.

Minimum number of the i-th row is 1 (1≤i≤n).

Minimum number of the j-th column is 1 (1≤j≤n).

Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo (109+7).

These are the examples of valid and invalid grid when n=k=2.

思路:

Dp[i][j] 表示前i行有j列有1同时保证每一行都有1,考虑转移, 当转移上下两行列的1数相等时.

单独考虑, 1的列可以是任意值,但是必须存在一个1保证当前行存在1.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

LL C[300][300];

LL Dp[300][300];

LL M1[300], M2[300];

LL n, k;

int main()

{

    C[0][0] = C[1][0] = C[1][1] = 1;

    for (int i = 2;i <= 250;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])%MOD;

    }

    M1[0] = M2[0] = 1;

    cin >> n >> k;

    for (int i = 1;i <= n;i++)

        M1[i] = (M1[i-1]*k)%MOD, M2[i] = (M2[i-1]*(k-1))%MOD;

    //k^i

    for (int i = 1;i <= n;i++)

        Dp[1][i] = (C[n][i]*M2[n-i])%MOD;

    for (int i = 2;i <= n;i++)

    {

        for (int j = 1;j <= n;j++)

        {

            for (int p = j;p <= n;p++)

            {

                LL res = ((C[n-j][p-j]*M2[n-p])%MOD*M1[j])%MOD;

                if (p == j)

                    res = ((M1[j]-M2[j])*M2[n-j])%MOD;

                LL sum = (Dp[i-1][j]*res)%MOD;

                Dp[i][p] = (Dp[i][p]%MOD + sum + MOD)%MOD;

            }

        }

    }

    cout << Dp[n][n] << endl;

    return 0;

}