[cf] 594 div2/div1 C/A Ivan the Fool and the Probability Theory

前言

t a g : tag : tag:数学 dp 斐波那契 *1700 传送门 : 题意 : 给定一个 n ∗ m n*m n∗m的网格,询问有多少种黑白染色方案,使得每个格子最多有一个相同颜色相邻

数据范围 N , M ∈ 1 0 5 N,M \in 10^5 N,M∈105 思路 :

因为数据范围很大,不是状压方案数问题

因为我们回归到正常的状态分析

状态表示 : f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1]表示第 i i i个格子为黑色或者白色的方案数

显然一行上面, i − 1 i-1 i−1的格子 和 i − 2 i-2 i−2的格子 不同为 i i i的颜色

状态计算 :

f [ i ] [ 0 ] = f [ i − 1 ] [ 0 ] + f [ i − 2 ] [ 0 ] f[i][0]=f[i-1][0]+f[i-2][0] f[i][0]=f[i−1][0]+f[i−2][0] f [ i ] [ 1 ] = f [ i − 1 ] [ 1 ] + f [ i − 2 ] [ 1 ] f[i][1]=f[i-1][1]+f[i-2][1] f[i][1]=f[i−1][1]+f[i−2][1]

显然这是可以优化为一维的

f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i]=f[i-1]+f[i-2] f[i]=f[i−1]+f[i−2]

这只是横着放的时候

我们再考虑竖着放的时候

我们考虑行放置的时候,当第一行存在颜色相连的时候,第二行和第一行完全相反,后面亦然

则列同理

因此列的总方案数是 f [ m ] f[m] f[m]

后面我们再考虑其他情况显然的

0101010 0101010 0101010这种是不符合方案的,因为网格是可以翻转的

所以总方案数是 2 ∗ ( f [ n ] + f [ m ] − 1 ) 2*(f[n]+f[m]-1) 2∗(f[n]+f[m]−1)

当然因为答案必然是固定的,所以可以小范围打表出一个结论,正解代码之后放一个打表代码,显然就是一个广义斐波那契数列 code :

ll f[N];

void solve(){
	int n,m;cin>>n>>m;
	
	f[1] = 1;
	f[2] = 2;
	
	for(int i=3;i