第2题 棋盘(原始) 查看测评数据信息
有一个R行C列的棋盘，共有R×C个单元格子，每个单元格子都要放一个棋子，棋子只有黑色或者白色。
如果两个单元格子有公共边，那么称为相邻的格子。
如果一个棋盘满足所有相邻格子的棋子都是不同颜色，那么就称为“优美”棋盘;否则称为“普通”棋盘。
把棋盘上的一个黑色棋子变成一个白色棋子，需要耗费1个能量。
同理，把棋盘上的一个白色棋子变成一个黑色棋子，也需要耗费1个能量。
如果把一个“普通”棋盘变成“优美”棋盘，至少需要消耗D能量，那么该“普通”棋盘的代价就是D。
下面的“普通”棋盘的代价就是2，因为至少要消耗2个能量，才能变成“优美”棋盘
WBWBW
BWBWB
BBWWW
BWBWB
容易发现，代价是D的“普通”棋盘，可能有很多种。
求：总共有多少种不同的代价是D的“普通”棋盘？模1000000007。
输入格式
一行，3个整数，R,C,D。1<=R,C<=100, 0<=D<=100。
输出格式
一个整数。
输入/输出例子1
输入：
2 2 1
输出：
8
输入/输出例子2
输入：
9 4 15
输出：
135805043
样例解释
无
分析：
假设一个2*2棋盘，为优美棋盘
那么最终状态只可能是
WB BW
BW WB
因为相邻格子的棋子都是不同颜色
从优美棋盘到普通棋盘转换，就是用了D步
假设D=3
WB
BW
可能变成
WW
WB
但是！
我们关注一下题目里
下面的“普通”棋盘的代价就是2，因为至少要消耗2个能量，才能变成“优美”棋盘
这个普通棋盘可以是
变左上角的W为B，而不是右上角B，左下角B变W，所以应该是1代价才能变为优化
所以！结论1:
我们发现，代价*2超过棋盘的棋子（上面例子的3*2>2*2），这种情况是不存在的，因为会有更优解
所以答案为0
再假设D=2
还是那个优美棋盘，普通棋盘可以是
WW
WW
也可以是
BB
BB
有什么选法呢？C(4,2)，总棋盘里4个棋子选2个变色都行
但是注意一下可能会有重复情况
2种优美棋盘
可以分别转换为一个普通棋盘！
代价*2等于棋盘的棋子
答案要除2
2*C(r*c, d)/2
也就是
C(r*c,d)
再假设D=1
2种优美棋盘
4个棋子1个棋子变
C(4,1)，但是这里并不会重复
1.优美
WB
BW
转普通
WW
BW
2.优美
BW
WB
转普通
发现并不会重复
所以答案是2个棋盘的C(r*c, d)
也就是
代价*2小于棋盘的棋子
答案是2*C(r*c,d)
归纳整理一下，注意值比较大，用杨辉三角求解组合数，同时注意数组范围，杨辉数组开N*N会爆，N*M就够了
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
long long r, c, d, y[10005][115];
int main()
{
scanf("%lld%lld%lld", &r, &c, &d);
for (int i=1; i<=r*c+1; i++)
{
int t=i;
y[i][1]=1;
if (t>105) t=105;
y[i][t]=1;
for (int j=2; j<=t; j++)
y[i][j]=(y[i-1][j]+y[i-1][j-1])%MOD;
}
if (2*d>r*c) cout<<0;
else if (2*d==r*c) cout<<y[r*c+1][d+1]%MOD;
else if (2*d<r*c) cout<<2*y[r*c+1][d+1]%MOD;
return 0;
}
注意MOD！
标签：优美,WB,T2,南海区,普通,棋子,2023,棋盘,代价 From： https://www.cnblogs.com/didiao233/p/17923508.html