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

題意：已知a0,ax,ay ?a[i] = ax * a[i-1] + ay;

b0,bx,by ? ?b[i] = bx * b[i-1] + by;

求 ai*bi(0 < i <(n-1)) 的和；

ac代碼：

/** *設前n想和為sum[n],則： * a[n]*b[n] = a[n-1]*b[n-1]*ax*bx + a[n-1]*ax*by + b[n-1]*ay*bx + ay * by; * * * { 1 0 0 0 0 } * { ax*bx ax*bx 0 0 0 } *{sum[n],a[n-1]*b[n-1],a[n-1],b[n-1],1} = {sum[n-1],a[n-2]*b[n-2],a[n-1],b[n-2],1}*{ ax*by ax*by ax 0 0 } * { ay*bx ay*bx 0 bx 0 } * { ay*by ay*by ay by 1 } * * * **/#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef __int64 LL; #define mod 1000000007 struct Z{LL m[5][5];Z(){memset(m,0,sizeof(m));}void init(){for(int i = 0;i < 5;i++)m[i][i] = 1;} }; Z operator * (Z a, Z b){Z c;for(int i = 0;i < 5;i++)for(int k = 0;k < 5;k++)for(int j = 0;j < 5;j++)c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j])%mod;return c; } Z Pow(Z a,LL x){Z ret;ret.init();while(x){if(x & 1) ret = ret * a;a = a * a;x >>= 1;}return ret; } int main(){LL n,a0,ax,ay,b0,bx,by;while(cin >> n){cin >> a0 >> ax >> ay;cin >> b0 >> bx >> by;LL k = a0 * b0 % mod;if(n == 0){cout << 0 <<endl;continue;}Z s;s.m[0][0] = 1;s.m[1][0] = ax*bx%mod;s.m[1][1] = ax*bx%mod;s.m[2][0] = ax*by%mod;s.m[2][1] = ax*by%mod;s.m[2][2] = ax%mod;s.m[3][0] = ay*bx%mod;s.m[3][1] = ay*bx%mod;s.m[3][3] = bx%mod;s.m[4][0] = ay*by%mod;s.m[4][1] = ay*by%mod;s.m[4][2] = ay%mod;s.m[4][3] = by%mod;s.m[4][4] = 1;s = Pow(s,n-1);LL ans = (s.m[0][0]*k + s.m[1][0]*k + s.m[2][0]*a0 + s.m[3][0]*b0 + s.m[4][0])%mod;cout << ans << endl;} }

總結

以上是生活随笔為你收集整理的hdu-4686 Arc of Dream的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。