题意：一个字符串由a,b组成，字符串转化为下一个的规则为：a->b，b->ab，告诉你，第n个、第m个字符串的长度，算第k个的长度
思路：这个变化规则，我们可以发现长度的变化是斐波拉契数列，我们设第1项有q个a，p个b，往下推，q、p前面的系数也是斐波拉契数列，我们快速幂算第n、m项q、p的前的系数，a1*q+b1*p = 第n项的长度，解二元一次方程，算出q、p算第k项
解方程：ax + by = m；cx + dy = n
有无实数解：yu1 = (md-bn) % (ad-bc)；yu2 = (mc-an) % (bc-ad)； 判断余数，余数都为0，有解
解：x = (md-bn) / (ad-bc)；y = (mc-an)/(bc-ad)
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 5; typedef long long ll; int MOD,N; struct data { ll s[maxn][maxn]; }res,tp; void init() { N = 2; memset(res.s,0,sizeof res.s); memset(tp.s,0,sizeof tp.s); res.s[1][1] = 1;res.s[2][2] = 1; tp.s[1][1] = 1;tp.s[1][2] = 1; tp.s[2][1] = 1;tp.s[2][2] = 0; } struct data mat(struct data &x,struct data &y) { struct data temp; memset(temp.s,0,sizeof temp.s); for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { for(int k = 1; k <= N; k++) { temp.s[i][j] = (temp.s[i][j] + x.s[i][k] * y.s[k][j]) % MOD; } } } return temp; } struct data mpow(struct data &a,ll b) { while(b) { if(b&1) res = mat(res,a); b >>= 1; a = mat(a,a); } return res; } int main(void) { ll n,m,x,y,k,q1,q2,p1,p2,p,q; int kase = 1,T; MOD = 1e9+7; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld%lld%lld",&n,&x,&m,&y,&k); if(n > m) { swap(n,m); swap(x,y); } q1 = q2 = p1 = p2 = 0; flag = 1; init(); if(n == 1) { q1 = 1; p1 = 1; } else { res = mpow(tp,n-2); q1 = ( res.s[1][1] * 1 + res.s[1][2] * 1 ) % MOD; p1 = ( res.s[1][1] * 2 + res.s[1][2] * 1 ) % MOD; } init(); if(m == 1) { q2 = 1; p2 = 1; } else { res = mpow(tp,m-2); q2 = ( res.s[1][1] * 1 + res.s[1][2] * 1 ) % MOD; p2 = ( res.s[1][1] * 2 + res.s[1][2] * 1 ) % MOD; } printf("Case %d: ",kase++); if( (x*p2-p1*y)%(q1*p2-p1*q2) || (x*q2-q1*y)%(p1*q2-q1*p2) ) printf("Impossible\n"); else { q = (x*p2-p1*y)/(q1*p2-p1*q2); p = (x*q2-q1*y)/(p1*q2-q1*p2); if(q < 0 || p < 0) printf("Impossible\n"); else { init(); ll ans; if(k == 1) ans = q+p; else { res = mpow(tp,k-2); ans = res.s[1][2] * (p+q)%MOD + res.s[1][1] * (2*p+q)%MOD; } ans %= MOD; printf("%lld\n",ans); } } } return 0; }
