思路：容易知道G(x)=6x，H(x)=6F(x)。此题的关键是求出F(x)的通项，要求F(x)的通项，先建立递推式：F(x)=1/6 * (F(x-1)+1) + 5/6 * (F(x-1)+1+F(x)-1)。
红色部分的意思是：假设已经连续出现x-1个了，若再出现一个同样的，总共花费F(x-1)+1步到达了目标状态，这种情况的概率是1/6，若出现了一个不一样的，则总共花费F(x-1)+1+F(x)-1，黄色部分是当前的总花费，但由于没到达目标状态，而回到了只比初始状态少走一步的状态，所以应该总花费应该加上F(x)-1，而概率是 5/6。将F(x)化简得到F(x)=6*F(x-1)+1，进而得到F(x) = (6^x-1)/5, H(x) = 6 * F(x), G(x) = 6 * x。求出通项来后就是解模方程了，由于有除法，用除法取模公式或者求逆都行。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <queue>#include <cmath>#include <algorithm>using namespace std;int pow_mod(int a, int b, int md) { if (b == 0) return 1 % md; long long buf = pow_mod(a, b >> 1, md); buf = (buf * buf) % md; return buf * (b & 1? a : 1) % md;}int solve(int k, int n) { int buf = (pow_mod(6, n, k) + k - 1) % k; if (buf == 0) return (pow_mod(6, n, k * 2011) + k * 2011 - 1) % (k * 2011) / k; else return (pow_mod(6, n, k * 2011) + k - buf - 1) % (k * 2011) / k;}int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int n; while (cin >> n, n) { cout << solve(30, n) << " " << solve(5, n) << endl; } return 0;} |