NC14546. 音乐转换
描述
John是一位热衷的音游爱好者。
一天，他正在玩音游，碰到了一个难题。他面前有一个初始旋律，游戏目标是要把这一段初始旋律变成目标旋律。但是，难点在于，John并不能随意的改变这一旋律，每一次改变之后的旋律必须在他的旋律库中（或者为目标旋律），更令人头疼的是，每一次操作都需要消耗一定的combo，我们假设从A旋律改变成B旋律，那么这一次操作所消耗的Combo数是A与B的最大子旋律长度（最大公共子序列）再加1。需要注意的是，初始旋律必须变成旋律库中的一个旋律或者直接变成目标旋律，而旋律库中的任意一个旋律可以变成旋律库中的另外一个旋律，或者直接变成目标旋律，也可以变成初始旋律。而目标旋律则不能再进行任何操作。
John想问问你，在不限操作次数的情况下，一共有多少种方案使得初始旋律变成目标旋律，且一共消耗的combo数恰好为T，当然这个答案太大了，你只需要将它对1,000,000,007取余数就可以了。
请注意，再本题中，所有的旋律你都可以视为一个字符串。
输入描述
输入第一行有两个正整数，分别为n和T，其中n代表曲库中的旋律数，T代表John所希望消耗的Combo数。
第二行有一个字符串，代表初始旋律。
第三行有一个字符串，代表目标旋律。
接下来N行，每行有一个字符串，代表旋律库中的旋律。
1<=N<=25
1<=T<=10^9
任意出现的一个字符串长度<=25
任意两个字符串的最长公共子序列的长度<=5
输入的n+2的字符串两两不同，且均由小写字母组成。
输出描述
输出只有一个正整数，代表方案数对1,000,000,007的余数。
示例1
输入:
2 4 ab ba bb aa
输出:
2
C++14(g++5.4) 解法, 执行用时: 984ms, 内存消耗: 1656K, 提交时间: 2019-02-06 20:48:12
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int maxn = 30;
char s[maxn][maxn];
int len[maxn];
int c[maxn][maxn];
int f[maxn][maxn];
int n, T;
long long dp[maxn][maxn];
struct M {
int r, c;
long long a[200][200];
};
M mul(const M &a, const M &b) {
M res;
res.r = a.r;
res.c = b.c;
for(int i = 0; i < res.r; i ++) {
for(int j = 0; j < res.c; j ++) {
res.a[i][j] = 0;
}
}
for(int j = 0; j < res.c; j ++) {
for(int k = 0; k < a.c ; k ++) {
if(b.a[k][j] == 0) continue;
for(int i = 0; i < res.r; i ++) {
long long u = a.a[i][k] * b.a[k][j] % mod;
res.a[i][j] = (res.a[i][j] + u) % mod;
}
}
}
return res;
}
int work(int x, int y) {
for(int i = 0; i <= len[x]; i ++) {
for(int j = 0; j <= len[y]; j ++) {
f[i][j] = 0;
}
}
for(int i = 1; i <= len[x]; i ++) {
for(int j = 1; j <= len[y]; j ++) {
f[i][j] = max(f[i- 1][j], f[i][j - 1]);
if(s[x][i - 1] == s[y][j - 1]) {
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return f[len[x]][len[y]] + 1;
}
int main() {
while(~scanf("%d%d", &n, &T)) {
scanf("%s", s[0]);
scanf("%s", s[n + 1]);
for(int i = 1; i <= n; i ++) {
scanf("%s", s[i]);
}
for(int i = 0; i <= n + 1; i ++) {
len[i] = strlen(s[i]);
}
for(int i = 0; i <= n + 1; i ++) {
for(int j = 0; j <= n + 1; j ++) {
c[i][j] = -1;
}
}
for(int i = 0; i <= n; i ++) {
for(int j = 0; j <= n; j ++) {
if(i == j) continue;
c[i][j] = work(i, j);
}
}
for(int j = 0; j <= n; j ++) {
c[j][n + 1] = work(j, n + 1);
}
for(int i = 0; i <= n + 1; i ++) {
for(int j = 0; j <= 10; j ++) {
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for(int j = 1; j <= 20; j ++) {
for(int i = 0; i <= n + 1; i ++) {
for(int k = 0; k <= n + 1; k ++) {
if(c[k][i] == -1) continue;
if(j - c[k][i] >= 0) {
dp[i][j] = (dp[i][j] + dp[k][j - c[k][i]]) % mod;
}
}
}
}
if(T <= 10) {
printf("%lld\n", dp[n + 1][T]);
continue;
}
M A;
A.r = 6 * (n + 2);
A.c = 6 * (n + 2);
for(int i = 0; i < A.r; i ++) {
for(int j = 0; j < A.c; j ++) {
A.a[i][j] = 0;
if(i == j) A.a[i][j] = 1;
}
}
M B;
B.r = 6 * (n + 2);
B.c = 6 * (n + 2);
for(int i = 0; i < B.r; i ++) {
for(int j = 0; j < B.c; j ++) {
B.a[i][j] = 0;
}
}
for(int j = 0; j < B.c; j ++) {
if(j % 6 != 5) {
B.a[j + 1][j] = 1;
} else {
for(int k = 0; k <= n + 1; k ++) {
if(c[k][j / 6] == -1) continue;
B.a[k * 6 + 6 - c[k][j / 6]][j] = 1;
}
}
}
M C;
C.r = 1;
C.c = 6 * (n + 2);
for(int j = 0; j < C.c; j ++) {
C.a[0][j] = dp[j / 6][j % 6];
}
int p = T - 5;
while(p) {
if(p & 1) A = mul(A, B);
B = mul(B, B);
p = p / 2;
}
C = mul(C, A);
printf("%lld\n", C.a[0][C.c - 1]);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 756ms, 内存消耗: 1296K, 提交时间: 2020-08-11 08:30:26
#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=1e9+7;
int n,x,t,dp[30][30];
struct mat{
int a[200][200];
}m,u;
char s[30][30];
mat matmul(mat c,mat d){
int h=n*6;
mat tmp;
for(int i=1;i<=h;i++)
for(int j=1;j<=h;j++){
tmp.a[i][j]=0;
for(int k=1;k<=h;k++)
tmp.a[i][j]=(tmp.a[i][j]+1LL*c.a[i][k]*d.a[k][j]%mod)%mod;
}
return tmp;
}
void matpow(int b){
for(int i=1;i<=6*n;i++)u.a[i][i]=1;
while(b){
if(b&1)u=matmul(u,m);
m=matmul(m,m);
b>>=1;
}
printf("%d",u.a[1][2]);
}
int solve(int a,int b){
memset(dp,0,sizeof(dp));
int ans=0;
int lena=strlen(s[a]+1),lenb=strlen(s[b]+1);
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++)
if(s[a][i]==s[b][j])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++)
ans=max(ans,dp[i][j]);
return ans+1;
}
int main(){
scanf("%d%d",&n,&t);n+=2;
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=5;j++)m.a[i+j*n][i+n*(j-1)]=1;
if(i==2)continue;
for(int j=1;j<=n;j++){
if(i==j)continue;
x=solve(i,j);
// cout<<i<<" "<<j<<" "<<x<<"\n";
m.a[i][j+n*(x-1)]=1;
}
}
matpow(t);
return 0;
}