Ural Timus 1009 K-based Numbers （dp+矩阵快速幂+快速乘）-白红宇

Ural Timus 1009 K-based Numbers （dp+矩阵快速幂+快速乘）

阅读量：5166 次

发布时间：2019-06-13

本文共 1302 字，大约阅读时间需要 4 分钟。

题解思路：

首先这此题是不准出现前导0和连续俩个位为0;

也就是如果是101进制，表示(100)10是(100)100 是有效的;

首先dp[i]表示第i位有多少个有效数字;

若i-1位为0 有效的数字 dp[i-2]*(k-1);

若i-1位不为0 有效的数字 dp[i-1]*(k-1);

所以 dp[i][j]=(dp[i-2]+dp[i-1])*(k-1);

数据非常大 2 ≤ N, K, M ≤ 10^18. 用矩阵优化;

构造矩阵

0 1 dp[0];

k-1 k-1 dp[1];

还是数据的原因，10^18*10^18 会爆ll; 要用快速乘

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define int long longconst int maxn=1e5+10;using namespace std;struct Matrix{ int nmap[3][3];};Matrix I={ 1,0,0, 0,1,0, 0,0,1,};Matrix T={ 0,0,0, 0,0,0, 0,0,0,};int smul(int a,int b,int mod){ int s=0; while(b) { if(b&1) s=(s+a)%mod; b>>=1; a=(a+a)%mod; } return s%mod;}Matrix Matrix_mul(Matrix a,Matrix b,int mod){ Matrix A=T; for(int k=1;k<=2;k++) { for(int i=1;i<=2;i++) { if(a.nmap[i][k]) for(int j=1;j<=2;j++) { A.nmap[i][j]+=smul(a.nmap[i][k],b.nmap[k][j],mod); A.nmap[i][j]%=mod; } } } return A;}Matrix Matrix_s(Matrix a,int b,int mod){ Matrix A=I; while(b) { if(b&1) A=Matrix_mul(A,a,mod); b>>=1; a=Matrix_mul(a,a,mod); } return A;}void put(Matrix a){ for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { cout<
             
              <<" "; } cout<