题目
Lambda受任于某情报站，他的工作是获取敌人情报。一次他在破解密码系统时，得到了一个N位B进制数φ，满足φ≡V (mod M)。他发现组成φ的数字很奇特。为了验证φ的特殊性，他将所有模M为V的N位B进制数，按照各数位构成的集合分类，并想知道每一类数各有多少个。
思路
这题的方法比较妙。
首先我们暴力DP的话n是每次+1的，这样太慢了。
考虑合并两个状态：
如果把动态规划中一个阶段的决策和转移，看成定义在状态空间上的函数，那么这种方法相当于计算转移函数的复合函数，不妨将其定义为转移函数的积。
由于其满足结合律，通过快速幂，它可以与矩阵乘法一样做
代码
#include<bits/stdc++.h>
using namespace std;
const int mod=10007,N=(1<<8)+1;
int f[N],g[N],F[N],ans[2048],n,m,b,v,mx,B;
int main()
{
scanf("%d%d%d%d",&n,&b,&m,&v);
mx=1<<b,--n;
for(int s=1; s<mx; s++)
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=0; i<b; i++) if(s&1<<i) ++f[i%m];
for(int i=1; i<b; i++) if(s&1<<i) ++g[i%m];
B=b%m;
for(int i=n; i; i>>=1)
{
if(i&1)
{
memset(F,0,sizeof(F));
for(int j=0; j<m; j++) if(g[j]) for(int k=0; k<m; k++) if(f[k])
(F[(j*B+k)%m]+=g[j]*f[k]%mod)%=mod;
memcpy(g,F,sizeof(F));
}
memset(F,0,sizeof(F));
for(int j=0; j<m; j++) if(f[j]) for(int k=0; k<m; k++) if(f[k])
(F[(j*B+k)%m]+=f[j]*f[k]%mod)%=mod;
memcpy(f,F,sizeof(F));
B=B*B%m;
}
ans[s]=g[v];
for(int t=s-1&s; t; t=t-1&s)
{
ans[s]-=ans[t];
if(ans[s]<0) ans[s]+=mod;
}
for(int i=b-1; i>=0; i--) if(s&1<<i) printf("%d",i);
printf(" %d\n",ans[s]);
}
}