bnu 34985 Elegant String（矩陣快速冪+dp推導公式）

bnu 34985 Elegant String（矩陣快速冪+dp推導公式）

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