Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

 

We define a kind of strings as elegant string: among all the substrings of an elegant string, none of them is a permutation of "0, 1,…, k".

Let function(n, k) be the number of elegant strings of length n which only contains digits from 0 to k (inclusive). Please calculate function(n, k).

 

 

Input starts with an integer T (T ≤ 400), denoting the number of test cases.

 

Each case contains two integers, n and k. n (1 ≤ n ≤ 10¹⁸) represents the length of the strings, and k (1 ≤ k ≤ 9) represents the biggest digit in the string.

 

 

For each case, first output the case number as "Case #x: ", and x is the case number. Then output function(n, k) mod 20140518 in this case. 

 

 

2

1 1

7 6

 

Case #1: 2

Case #2: 818503

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 typedef long long LL;

 const LL p = ;

 struct Matrix

 {

     LL mat[][];

     void init()

     {

         memset(mat,,sizeof(mat));

     }

     void first(int n)

     {

         int i,j;

         for(i=;i<=n;i++)

             for(j=;j<=n;j++)

                 if(i==j)mat[i][j]=;

         else mat[i][j]=;

     }

 }M_hxl,M_tom;

 Matrix multiply(Matrix cur,Matrix ans,int n)

 {

     Matrix now;

     now.init();

     int i,j,k;

     for(i=;i<=n;i++)

     {

         for(k=;k<=n;k++)

         {

             for(j=;j<=n;j++)

             {

                 now.mat[i][j]=now.mat[i][j]+cur.mat[i][k]*ans.mat[k][j];

                 now.mat[i][j]%=p;

             }

         }

     }

     return now;

 }

 Matrix pow_mod(Matrix ans,LL n,LL m)

 {

     Matrix cur;

     cur.first(m);

     while(n)

     {

         if(n&) cur=multiply(cur,ans,m);

         n=n>>;

         ans=multiply(ans,ans,m);

     }

     return cur;

 }

 LL solve(LL n,LL k)

 {

     M_hxl.init();

     int i,j;

     for(i=;i<=k-;i++)M_hxl.mat[][i]=;

     for(i=;i<=k-;i++)

     {

         for(j=;j<=k-;j++)

         {

             if(i-j>)continue;

             if(i-j==) M_hxl.mat[i][j]=k-i+;

             else M_hxl.mat[i][j]=;

         }

     }/**ok**/

     M_tom = pow_mod(M_hxl,n,k-);

     LL sum=(M_tom.mat[][]*k)%p;

     return sum;

 }

 int main()

 {

     int T,t;

     LL n,k;

     scanf("%d",&T);

     for(t=;t<=T;t++)

     {

         scanf("%lld%lld",&n,&k);

         k++;

         LL ans=solve(n,k);

         printf("Case #%d: %lld\n",t,ans);

     }

     return ;

 }