【CF497E】Subsequences Return
题意：设$s_k(x)$表示x在k进制下各位数的和mod k的值。给出k，现有序列$s_k(1),s_k(2),...s_k(n)$。求这个序列有多少个本质不同的子序列。
$n\le 10^{18},k\le 30$
题解：状态非常巧妙（其实做过类似套路就知道了）。看到$n=10^{18}$就一定是让你矩乘了。我们希望构建出一个类似于自动机的东西，它能识别出一个序列的所有子序列，且点数最好是在$O(k)$级别的，怎么办呢？
假如我们真的构建出了一个自动机，那么对于他的一个状态x，现在新来了一个数a，如果a是x想要的，那么从x转移到其它状态，否则转移到自己。那我们不妨直接设x这个状态表示它下一个想要的数是x的方案数。如果匹配成功，则下一个想要的数可以是任意数，并使计数器+1，否则它想要的数还是自己。
接着考虑怎么矩乘，容易想到将x放到k进制下表示。用$A_{i,j}$表示$s_k(j\times k^i)..s_k((j+1)\times k^i-1)$这段数对应的转移矩阵。那么$A_{i,j}$其实就是$A_{i-1,j}A_{i-1,j+1}...A_{i-1,k-1}A_{i-1,0}...A_{i-1,j-1}$。用前缀和优化一下即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll P=1000000007;
int m,len;
ll n;
ll v[61];struct M
{ll v[31][31];M () {memset(v,0,sizeof(v));}ll * operator [] (const int &a) {return v[a];}M operator * (const M &a) const{M b;int i,j,k;for(i=0;i<=m;i++) for(j=0;j<=m;j++) for(k=0;k<=m;k++) b.v[i][j]=(b.v[i][j]+v[i][k]*a.v[k][j])%P;return b;}
}T[60][30],S,s1[60][30],s2[60][30];int main()
{scanf("%lld%d",&n,&m);v[0]=n;while(v[len]) v[len+1]=v[len]/m,v[len]%=m,len++;int i,j,a,b;for(i=0;i<=m;i++) S[0][i]=1;for(i=0;i<len;i++){for(j=0;j<=m;j++) T[i][0][j][j]=1;if(!i){for(j=0;j<m;j++){T[i][j][m][m]=1;for(a=0;a<m;a++){if(a!=j){T[i][j][a][a]=1;continue;}for(b=0;b<=m;b++) T[i][j][a][b]=1;}}}else{for(j=0;j<m;j++){if(!j) T[i][j]=s2[i-1][0];else T[i][j]=s2[i-1][j]*s1[i-1][j-1];}}for(s1[i][0]=T[i][0],j=1;j<m;j++) s1[i][j]=s1[i][j-1]*T[i][j];for(s2[i][m-1]=T[i][m-1],j=m-2;j>=0;j--) s2[i][j]=T[i][j]*s2[i][j+1];}for(i=len-1,j=0;i>=0;i--){while(v[i]--) S=S*T[i][j],j=(j+1)%m;}printf("%lld",S[0][m]);return 0;
}//1000000000000000000 2