【CF497E】Subsequences Return 矩阵乘法

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

【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];
elseT[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