2016-10-10

HDU 5863 cjj's string game【dp+矩阵快速幂】

题目链接：

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

题意：

用$k$个不同的字符组成两个长度为$n$字符串，要求两个字符串连续的相同部分长度最大为$m$，问有多少种构造方法。
数据范围：$1 \le n \le 1000000000, 1 \le m \le 10, 1 \le k \le 26 $

分析：

首先我们可以设计出状态$dp[i][j]:= 考虑了前$i$个字符，其中最后$j$个相等的方案数$，
得到状态转移方程:
$dp[i][j] = dp[i - 1][j - 1]$
$dp[i][0] = \sum_{j=0}^m dp[i - 1][j]$
最后答案为相等字符个数小于等于$m$的方案数，再求个小于等于$m-1$的方案数，相减一下即为正好为$m$的方案数。
$n$有$1e9$，观察转移方程，发现可以利用矩阵快速幂进行优化。
还可以设计状态
$dp[i][j][0]$考虑了前$i$个字符，其中最后$j$个相等，且前面还没有连续的$m$个相等的方案数
$dp[i][j][1]$则表示已经有连续$m$个相等的出现的方案数。
同样矩阵快速幂优化，这样构造出的矩阵稍麻烦一些。

代码：

/*************************************************************************
    > File Name: 5863.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/10 19:58:36
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 15;
struct Matrix
{
    int row,cal;
    long long m[N][N];
};
Matrix init(Matrix a, long long t)
{
    for(int i = 0; i < a.row; i++)
        for(int j = 0; j < a.cal; j++)
            a.m[i][j] = t;
    return a;
}
Matrix operator * (const Matrix& a, const Matrix& b)
{
    Matrix ans;
    ans.row = a.row, ans.cal = b.cal;
    ans = init(ans,0);
    for(int i = 0; i < a.row; i++)
        for(int j = 0; j < b.cal; j++)
            for(int k = 0; k < a.cal; k++)
                ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j])%mod;
    return ans;
}
int m, k;
void print(Matrix I)
{
	for(int i = 0; i < I.row; ++i){
		for(int j = 0; j < I.cal; ++j){
			printf("%d ", I.m[i][j]);
		}
		puts("");
	}
}
ll gao(int m, long long b)
{
	Matrix A;
	A.row = A.cal = m + 1;
	A = init(A, 0);
	for(int i = 0; i <= m; ++i){
		for(int j = 0; j <= m; ++j){
			if(i == 0) A.m[i][j] = k * (k - 1);
			else{
				if(i == j + 1) A.m[i][j] = k;
			}
		}
	}
	Matrix I;
	I.row = m + 1, I.cal = 1;
	I = init(I, 0);
	I.m[0][0] = 1;
	for(; b; b >>= 1, A = A * A){
		if(b & 1) I = A * I;
	}
	ll ans = 0;
	for(int i = 0; i <= m; ++i){
		ans = (ans + I.m[i][0]) % mod;
	}
	return ans;
}
int main (void)
{
	int T;scanf("%d", &T);
	while(T--){
		int n;scanf("%d%d%d", &n, &m, &k);
		printf("%lld\n", (gao(m, n) - gao(m - 1, n) + mod) % mod);
	}
	return 0;
}