Codeforces Round #589 (Div. 2) E. Another Filling the Grid(DP, 组合数学)
2024-09-05 05:55:52
链接:
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;
}
最新文章
- Signalr系列之虚拟目录详解与应用中的CDN加速实战
- VC程序获取管理员权限
- MySQL时间分组查询
- C# 在執行程式目錄下產生文件夾
- Java并发编程实例(synchronized)
- 深度解析Java8 – AbstractQueuedSynchronizer的实现分析(下)
- 【Android】Activity生命周期(亲测)
- jstack命令(Java Stack Trace)
- Spring 3.x企业应用开发实战(14)----事务
- 网易云课堂_程序设计入门-C语言_期末考试编程题
- 自己实现的Boost库中的lexical_cast随意类型转换
- 简单实现Android平台多语言
- threading多线程总结
- cnblogs第一天
- 实战开发-》融云tp3.2.3
- Pycharm 2018.2.1最新版破解到2099年图解教程
- C++ STL标准容器插入删除算法的复杂度
- 应收事物处理删除 SQL 语句
- jvm高级特性(5)(1)(原子性,可见性,有序性,volatile,概述)
- 使用CAReplicatorLayer [2]