[矩阵快速幂 优化DP] 51Nod 1311 转换机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
	return *p1++;
}

inline void read(ll &x)
{
	char c=nc(),b=1;
	for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
	for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
	char c=nc(); int len=0;
	for (;!(c>='a' && c<='c');c=nc()); 
	for (;c>='a' && c<='c';s[++len]=c,c=nc()); s[len+1]=0; return len; 
}

const int P=1000000007;
const int N=105;
const int L=15; 

struct Matrix{
	int n; ll a[N][N];
	Matrix(int _n=0){
		n=_n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=0;
	}
	ll *operator [](int x){
		return a[x];
	}
	friend Matrix operator *(Matrix &A,Matrix &B){
		int n=A.n;
		Matrix ret(n);
		for (int k=1;k<=n;k++)
			for  (int i=1;i<=n;i++)
				for (int j=1;j<=n;j++)
					(ret[i][j]+=A[i][k]*B[k][j])%=P;
		return ret;
	}
}I,A;

int len; ll ans,step;
char S[L],T[L];
int sum[3];
int cnt,hash[L][L];

inline Matrix Pow(Matrix a,ll b){
	Matrix ret=I;
	for (;b;b>>=1,a=a*a)
		if (b&1)
			ret=ret*a;
	return ret;
}

int main()
{
	ll isum=0,bsum=0; ll m,c0,c1,c2; ll a,b,c;
	freopen("goldendragonfish.in","r",stdin);
	freopen("goldendragonfish.out","w",stdout);
	len=read(S); read(T);
	read(c0); read(c1); read(c2);  read(m);
	for (int i=1;i<=len;i++)
	{
		if (S[i]==T[i]) a=0,b=0;
		if (S[i]=='a' && T[i]=='b') a=c0,b=1;
		if (S[i]=='b' && T[i]=='c') a=c1,b=1;
		if (S[i]=='c' && T[i]=='a') a=c2,b=1;
		if (S[i]=='a' && T[i]=='c') a=c0+c1,b=2;
		if (S[i]=='b' && T[i]=='a') a=c1+c2,b=2;
		if (S[i]=='c' && T[i]=='b') a=c2+c0,b=2;
		isum+=a; bsum+=b; sum[b]++;
	}
	if (m<isum) return printf("0n"),0;
	step=bsum+(m-isum)/(c0+c1+c2)*3;
	for (int i=0;i<=len;i++)
		for (int j=0;i+j<=len;j++)
			hash[i][j]=++cnt;
	A=I=Matrix(cnt+1);
	for (int i=1;i<=cnt+1;i++) I[i][i]=1;
	for (int i=0;i<=len;i++)
		for (int j=0;i+j<=len;j++)
		{
			a=i,b=j,c=len-i-j;
			if (a)
				A[hash[a-1][b]][hash[a][b]]=a;
			if (b)
				A[hash[a+1][b-1]][hash[a][b]]=b;
			if (c)
				A[hash[a][b+1]][hash[a][b]]=c;
		}
	A[cnt+1][hash[len][0]]=A[cnt+1][cnt+1]=1;
	A=Pow(A,step+1);
	ans=A[cnt+1][hash[sum[0]][sum[1]]];
	printf("%lldn",ans);
	return 0;
}