题解 | #填数游戏#
填数游戏
http://www.nowcoder.com/practice/4cce3022cab449039f0075e6665d53c7
题意：
有
个格子，每个格子都可以填写
四个整数，现在问你有多少种方案，使得最后所填数字中相同的偶数出现的次数也是偶数次？
解法一（动态规划，不可AC）
我们设：
一. 我们考虑转移
（1）尝试从
转移
即
（2）尝试从
转移
即
（3）尝试从
转移
（4）尝试从
转移
前面有奇数个
和奇数个
，故无法只填写一个数字使满足有偶数个和偶数个，故无法转移
综上所述，
二. 我们考虑转移
（1）尝试从转移
即
（2）尝试从转移
即
（3）尝试从转移
前面有奇数个和偶数个，故无法只填写一个数字使满足有偶数个和奇数个，故无法转移
（4）尝试从转移
即
综上所述，
类似的，我们可以用上面的方法推导出：
最后，我们考虑答案：
显然答案是有偶数个和偶数个的方案数，即
代码：
class Solution {
public:
const int mod=1e9+7;
//0 偶数个2偶数个4
//1 偶数个2奇数个4
//2 奇数个2偶数个4
//3 奇数个2奇数个4
int f[1000000001][4];
int GetNumberOfSchemes(int n) {
f[1][0]=2;//第1个格子0个2和0个4，两种方案：1、3
f[1][1]=1;//第1个格子0个2和1个4，一种方案：4
f[1][2]=1;//第1个格子1个2和0个4，一种方案：2
f[1][3]=0;//第1个格子1个2和1个4，没有方案
for(int i=2;i<=n;i++){
f[i][0]=((f[i-1][0]*2%mod+f[i-1][1])%mod+f[i-1][2])%mod;//第一种
f[i][1]=((f[i-1][0]+f[i-1][1]*2%mod)%mod+f[i-1][3])%mod;//第二种
f[i][2]=((f[i-1][0]+f[i-1][2]*2%mod)%mod+f[i-1][3])%mod;//第三种
f[i][3]=((f[i-1][1]+f[i-1][2])%mod+f[i-1][3]*2%mod)%mod;//第四种
}
return f[n][0];
}
}; 时间复杂度：空间复杂度：
解法二（矩阵快速幂）
根据解法一所得到的递推式，我们可以构造如下矩阵乘法式子：
根据矩阵乘法满足结合律，我们又可得：
于是我们就可以愉快地解决这道题了！
代码：
class Solution {
public:
/**
*
* @param n int整型
* @return int整型
*/
static const int mod=1e9+7;
struct mat{
int A[4][4];
inline mat(){
memset(A,0,sizeof A);
}
inline mat operator * (const mat& other)const{//矩阵乘法
mat ret;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
ret.A[i][j]+=1ll*A[i][k]*other.A[k][j]%mod;
ret.A[i][j]%=mod;//注意取余数
}
}
}
return ret;
}
};
mat ksm(mat a,int b){
//矩阵快速幂算法
mat ret;
for(int i=0;i<4;i++)ret.A[i][i]=1;
while(b){
if(b&1){
ret=ret*a;
}
a=a*a;
b>>=1;
}
return ret;
}
int GetNumberOfSchemes(int n) {
mat t;
//初始化矩阵
t.A[0][0]=2,t.A[0][1]=1,t.A[0][2]=1,t.A[0][3]=0;
t.A[1][0]=1,t.A[1][1]=2,t.A[1][2]=0,t.A[1][3]=1;
t.A[2][0]=1,t.A[2][1]=0,t.A[2][2]=2,t.A[2][3]=1;
t.A[3][0]=0,t.A[3][1]=1,t.A[3][2]=1,t.A[3][3]=2;
t=ksm(t,n-1);//求矩阵的n-1次方
return ((1ll*2*t.A[0][0]%mod+t.A[0][1])%mod+t.A[0][2])%mod;//最后答案为f[n][0]，模拟矩阵乘法计算答案
}
}; 时间复杂度： 空间复杂度：)
，矩阵的大小是
的，故总的空间复杂度为
