HDU 5863 cjj's string game 矩阵优化DP

http://acm.split.hdu.edu.cn/showproblem.php?pid=5863

cjj's string game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

cjj has k kinds of characters the number of which are infinite. He wants to build two strings with the characters. The lengths of the strings are both equal to n.

cjj also define a cjj_val for two string.
a[i,j] means the substring a[i],a[i+1],...,a[j-1],a[j] of string a.

cjj_val = max({ j-i+1 }) where a[i,j]=b[i,j] for every 0<=i<=j<n.

Know cjj wants to know that if he wants to build two strings with k different characters whose cjj_val is equal to m, how many ways can he do that.

Input

The first line of the input data is an integer T(1<=T<=100), means the number of test case.

Next T lines, each line contains three integers n(1<=n<=1000000000), m(1<=m<=10), k(1<=k<=26).

Output

For each test case, print one line, the number of the ways to build the string. The answer will be very large, you just need to output ans mod 1000000007.

Sample Input

2
3 2 3
3 3 3

Sample Output

108
27

Author

BUPT

Source

 2016 Multi-University Training Contest 10 

题意

用k种不同的字符,构建两个字符串,它们的长度都为n,最长的相同位置的相同子串的长度为m,求方案数。1<=n<=109,1<=m<=10,1<=k<=26。

题解

用dp[i][d][j]表示构建了长度为i的字符串,是(d=1)否(d=0)已经达到过相同子串长度为m的状态,以当前位置结尾的相同子串的长度为j,的方案数。当j<m-1的时候,能够转移到j=0和j=j+1两个状态,分别表示下一位不同和下一位相同的两种情况。当j=m-1的时候,可以转移到j=0和d=1&&j=m两个状态,分别表示下一位不同和下一位相同的两种情况,注意,只要j=m的时候,d一定是1。当j=m的时候,就只能转移到j=0这个状态。总共的状态数也就2*m+1个,由于n很大,m很小,可以使用矩阵二分幂的方式来加速DP的转移。将状态重新编号,转移的方案数填入矩阵,跑矩阵二分幂即可。