1 条题解
-
-1
题目大意： 求存在相邻格子存在相同奇偶性的情况，和课上的最后一道例题属于同种类型。
思路
第 1 步，先求出情况总数：m^n
第 2 步，求出相邻格子奇偶性都各不同的情况：其中偶数有 m/2 个，奇数有 (m+1)/2 个。包含了两种小的情况： 如果第一个格子是奇数，那么共有(n+1)/2个格子需要填奇数，n/2个格子填偶数，方案数为： ((m+1)/2)^((n+1)/2) * (m/2)^(n/2) 如果第一个格子是偶数，那么共有(n+1)/2个格子需要填偶数，n/2个格子填奇数，方案数为： ((m+1)/2)^(n/2) * (m/2)^((n+1)/2)
第 3 步，用总数 m^n 减去第 2 步中的两种情况。
参考代码
long long fast_pow(long long a, long long x) { long long ans=1; while(x) { if (x % 2) ans = (ans * a) % MOD; a = (a * a) % MOD; x = x >> 1; } return ans; }cout << ((fast_pow(m,n) - fast_pow((m+1)/2,(n+1)/2)*fast_pow(m/2,n/2) - fast_pow((m+1)/2,n/2)*fast_pow(m/2,(n+1)/2))% MOD + MOD) % MOD << endl;
董一骏
MOD
@ 2024-2-2 17:00:37
- 1