题解：P12975 疯狂星期四
wflhx2011
·
·
题解
首先想到 dp。
设 f_{i,j} 表示从 1 到 i 的格子里数的和，对 7 取余余数为 j。
转移应为 f_{i,j}=f_{i-1,j}+\sum_{k=0}^6{f_{i-1,k}}，可以理解为后面的一部分是第 i 格填 0 到 6，前面是填 7。
时间复杂度 O(n)，可惜 n 太大，似乎无法优化。
发现对于相同的 i 来说，后面的求和是相同的，只有前面一部分影响 i 相同的 f_{i,j} 的值。当 i=1 时，不难发现 f_{1,0}=2，而 f_{1,1}=f_{1,2}=…=f_{i,6}=1。
所以，对于任意的 i，就都有 f_{i,0}=f_{i,1}+1=…=f_{i,6}+1。
又因为总共有 8^n 种方案，就有 f_{n,0}+6 \times (f_{n,0}-1)=8^n，解得 f_{n,0}=\frac {8^n+6}{7}。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=101;
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
char c;
while(cin>>c)
n=(n*10+(c-'0'))%100;
cout<<(ksm(8,n)+6)%mod*ksm(7,mod-2)%mod;
return 0;
}
```