Codeforces Round #594 (Div. 2) - C. Ivan the Fool and the Probability Theory(思维)
2024-08-27 12:41:10
题意:给n*m的网格涂黑白两种颜色,保证每个格子上下左右的四个格子中最多只有一个格子与自己颜色相同,问有多少种涂法?结果$mod1000000007$
思路:先只考虑一行有多少种涂法
- $dp[i][0]$表示第$i$个格子与第$i-1$个格子颜色不一样,那么第$i-1$与第$i-2$个格子颜色可以不同也可以相同,所以$dp[i][0]=dp[i-1][1]+dp[i-1][0]$
- $dp[i][1]$表示第$i$个格子与第$i-1$个格子颜色相同,那么第$i-1$与第$i-2$格子颜色只能不相同,所以$dp[i][1]=dp[i-1][0]$
再考虑其他行的情况:
- 第一行有两个连续格子颜色相同时的情况(即 黑黑白黑白...这种情况),这时第二行必须跟第一行完全相反才能符合题意。
证明如下:以 黑黑白黑白 为例,如果 黑黑 的下一行出现了 黑,显然不符合题意,所以 黑黑 的下一行只能为 白白,其次如果第三个 白 的下一行为 白,就和前面的两个 白 组成了连续的三个 白,不符合题意,所以此时下一行必须与上一行完全相反。
- 第一行没有两个连续格子颜色相同时的情况(即 黑白黑白黑白...这种情况),设$f(i)$表示加入第$i$行时有多少种情况,如果第$i-1$和第$i-2$行颜色相同,那么第$i$行与第$i-1$行颜色不能相同,如果第$i-1$和第$i-2$行颜色不同,那么第$i$行和第$i-1$行颜色可以相同也可以不同,先假设第$i$行与第$i-1$行颜色不同,那么有$f(i-1)$种,只有当第$i-1$行与第$i-2$行颜色不同时第$i$行与第$i-1$行颜色才能相同,有$f(i-2)$种,所以$f(i)=f(i-1)+f(i-2)$,满足斐波那契数列。
第一种情况有$dp[m][0]+dp[m][1]-2$种(除去 黑白黑白黑白... 白黑白黑白黑... 这两种情况),第二种情况只有两种,所以最后的方案数为$dp[m][0]+dp[m][1]-2+2*f(n)$
其实行和列都是斐波那契数列,比赛时没看出来,答案为$2*(f(n)+f(m))-2$
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; typedef long long ll; const int N = ;
const ll mod = int(1e9) + ; ll dp[N][], n, m;
ll f[N]; int main()
{
scanf("%lld%lld", &n, &m);
dp[][] = , dp[][] = ;
for (int i = ; i <= m; i++) {
dp[i][] = (dp[i - ][] + dp[i - ][]) % mod;
dp[i][] = dp[i - ][] % mod;
}
f[] = , f[] = ;
for (int i = ; i <= n; i++) f[i] = (f[i - ] + f[i - ]) % mod;
ll res = (dp[m][] + dp[m][]) % mod;
ll ans = ((f[n] * ) % mod + (res - ) % mod) % mod;
printf("%lld\n", ans);
return ;
}
最新文章
- EasyUI 中点击取消按钮关闭Dialog(对话框窗口)
- OOCSS的概念和思路
- WebForm Application Viewstate 以及分页(功能性的知识点)
- Unieap3.5-需要用到window.setTimeout的地方
- ASP.NET MVC之PagedList使用
- Deep Learning 学习随记(五)深度网络--续
- 10.Java 加解密技术系列之 DH
- 关于swagger——WebApi一个controller中出现多个Get是出现错误的处理
- 【Beta阶段】展示博客
- Factorial(hdu 1124)
- 【XSY1762】染色问题 网络流
- kafka入门2:java 创建及删除 topic
- android R.layout 中找不到已存在的布局文件
- day 2 Linux Shell笔记
- ORACLE system表空间满
- 大话存储4——RAID磁盘阵列
- Sparsity稀疏编码(一)
- Sequential Minimal Optimization(SMO,序列最小优化算法)初探
- python装饰器简单使用
- javascript总结11:JavaScript的自增自减