【CF497E】Subsequences Return 矩阵乘法
矩阵 乘法 return
2023-09-11 14:15:24 时间
【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
相关文章
- R语言——矩阵运算
- Java实现 蓝桥杯 算法提高 矩阵乘法(暴力)
- Java实现 LeetCode 519 随机翻转矩阵
- Java实现矩阵相乘问题
- Java实现 蓝桥杯 算法训练 矩阵乘法
- 浅谈压缩感知(七):常见测量矩阵的MATLAB实现
- LeetCode(74):搜索二维矩阵
- 【t004】切割矩阵
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-86 矩阵乘法
- 矩阵转置(transpose、T)
- 1.1 矩阵乘法介绍
- [转]如何理解矩阵乘法的规则
- torch.spmm矩阵乘法
- pytorch 中矩阵乘法
- 矩阵的左乘和右乘
- 最大子矩阵和
- 27 | SIMD:如何加速矩阵乘法?
- AI学习之路(19)TensorFlow里的矩阵乘法
- numpy中矩阵乘法,星乘(*)和点乘(.dot)的区别
- 【LeetCode】剑指 Offer II 107. 矩阵中的距离
- OpenCV(C++)图像处理基础02:矩阵的掩膜操作与Mat对象【提升图像对比度】
- EIE稀疏矩阵乘法硬件模拟