bnu 34985 Elegant String（矩阵快速幂+dp推导公式） - c++编程基础

Elegant String

Time Limit: 1000ms Memory Limit: 65536KB 64-bit integer IO format: %lld Java class name: Main Prev Submit Status Statistics Discuss Next 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

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 ≤ 1018) represents the length of the strings, and k (1 ≤ k ≤ 9) represents the biggest digit in the string.

Output

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.

Sample Input

2
1 1
7 6

Sample Output

Case #1: 2
Case #2: 818503

Source

2014 ACM-ICPC Beijing Invitational Programming Contest

题解及代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; typedef long long ll; const long long mod=20140518; struct mat { ll t[10][10]; void set() { memset(t,0,sizeof(t)); } } a,b; mat multiple(mat a,mat b,ll n,ll p) { ll i,j,k; mat temp; temp.set(); for(i=0; i
     
      >=1; b=multiple(b,b,n,p); } return t; } void init(ll k) { b.set(); for(ll i=0; i