题目描述
飞镖游戏虽好玩，但小老虎不忘考考同学的数学能力，为了好玩和不大难，小老虎想就用5个阿拉伯数吧。1、2、3、4、5数字组成一个N位的数（可以重复使用，也可以不用），有多少个数I，满足Imod3=1。
输入格式
一行，为1个整数N。
输出格式
一个数，即满足要求的数的个数mod100007。
输入样例
4
输出样例
208
数据规模
对于30%的数据，N≤8；
对于100%的数据，N≤1000000。
题解
相信大家小学都学过。一个数$mod 3$等于这个数的各位数字之和$mod 3$。
假设我们已经得到了一个$i$位的满足题目要求的数，这个时候，我们在$i+1$为添加$3$，一定还能满足题目要求。
但是，如果不添加$3$呢？
这里我们可以列举出来：
(1)当第$i$位为$1$时，我们可以改成$[2,2],[2,5],[3,1],[3,4],[5,2],[5,5]$（这里$[x,y]$表示第$i$位改成$x$，第$i+1$位添上$y$，下同）。共$6$种情况。
(2)当第$i$位为$2$时，我们可以改成$[1,1],[1,4],[3,2],[3,5],[4,1],[4,4]$。共$6$种情况。
(3)当第$i$位为$3$时，我们可以改成$[1,2],[1,5],[2,1],[2,4],[4,2],[4,5],[5,1],[5,4]$。共$8$种情况。
(4)当第$i$位为$4$时，我们可以改成$[2,2],[2,5],[3,1],[3,4],[5,2],[5,5]$。共$6$种情况。
(5)当第$i$位为$5$时，我们可以改成$[1,1],[1,4],[3,2],[3,5],[4,1],[4,4]$。共$6$种情况。
观察(1)(2)与(4)(5)其实是一样的，那我们将数量除以$2$即可。
我们可以设$c[i][0]$为第$i$位为$3$的符合题目要求的数量，$c[i][1]$为第$i$位不为$3$的符合题目要求的数量。
根据上面的方程可得，$c[i][0] = c[i - 1][0] + c[i - 1][1], c[i][1] = c[i - 1][0] imes 8 + c[i - 1][1] imes 3$。这里可以用滚动数组优化。
#include <iostream> #define MOD 100007 using namespace std; int n; int prev[2], now[2]; //最高位为3或不为3的符合条件的情况 int main() { cin >> n; now[1] = 2; while(--n) { prev[0] = now[0]; prev[1] = now[1]; now[0] = (prev[0] + prev[1]) % MOD; now[1] = (prev[0] * 8 + prev[1] * 3) % MOD; } cout << (now[0] + now[1]) % MOD;