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