VOJ 1067 Warcraft III 守望者的烦恼 (矩阵快速幂+dp)

题目链接

显然可知

dp[n] = dp[n-k] + dp[n-k+1] + ... +dp[n-1];

然后要用矩阵来优化后面的状态转移。

也就是矩阵

0 1 0 0 a b

0 0 1 0 * b = c

0 0 0 1 c d

1 1 1 1 d a+b+c+d

然后跑快速幂

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define N 10 using namespace std; const int mod = 7777777; typedef long long LL; struct matrix { LL a[10][10]; }origin; int n,m; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i
       
        >=1; A=multiply(A,A); } return res; } void print(matrix x) { for(int i=0;i
        
         >n>>k) { memset(origin.a,0,sizeof origin.a); origin.a[0][0]=1; for(int i=1;i<=n;i++) { origin.a[i][0]=1; for(int j=0;j