老虎的数学游戏
cjrqwq
·
·
个人记录
原题链接
老虎的数字游戏
描述
飞镖游戏虽好玩，但小老虎不忘考考同学的数学能力，为了好玩和不大难，小老虎想就用5个阿拉伯数吧。1、2、3、4、5数字组成一个N位的数(可以重复使用,也可以不用),有多少个数I,满足Imod3=1。
输入
第1行为1个整数N。
输出
输出一个数，即满足要求的数的个数mod 100007。
输入样例 1
4
输出样例 1
208
限制与注意
对于30%的数据，N≤8 对于100%的数据，N≤1000000
动态规划
定义状态
在动态规划里，定义奇怪正确的状态最重要的步骤之一。
在做很多动态规划时会发现，题目给出的信息都不能作为正确的状态。所以需要寻找状态。
余数
众所周知，x%3==x的数字和%3。
所以可以用余数来定义状态。
原问题与子问题
定义完状态，就可以定义数组 dp[3][11111] ,表示到第j位%3余数为i的数的数量。
初值
通过题目可以得知（其实就是把1~5依次填入）:
dp[0][1]=1;
dp[1][1]=2;
dp[2][1]=2;
状态转移方程
只要做完以上的铺垫，状态转移方程也就水到渠成了。
dp[0][i]=dp[0][i-1]+2*dp[1][i-1]+2*dp[2][i-1];
dp[1][i]=dp[1][i-1]+2*dp[0][i-1]+2*dp[2][i-1];
dp[2][i]=dp[2][i-1]+2*dp[0][i-1]+2*dp[1][i-1];
代码被吃了
其它
假设一下：假如有10个状态呢；
OIers们都知道，计算机是非常厉害的，所以计算机就是我们的免费劳动力。
让计算机来帮我们做，多是一件美事。
所以我们可以得出另一个状态转移方程：
dp[i][(j+k)%3]+=dp[i-1][j];
## 贴上某个热心同学贡献的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define mod 100007
int dp[1000000+10][5],n;
int main(){
scanf("%lld",&n);
dp[1][0]=1,dp[1][1]=2,dp[1][2]=2;
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++){
for(int k=1;k<=5;k++){
dp[i][(j+k)%3]+=dp[i-1][j];
dp[i][(j+k)%3]%=mod;
}
}
}
printf("%lld",dp[n][1]);
return 0;
}
```