本文共 2866 字,大约阅读时间需要 9 分钟。
又是逗比题...
然后就能构造矩阵了
重构了一下快速幂...感觉很爽很好用...直接a^b就搞定
/********************* Template ************************/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define EPS 1e-8#define MAXN 10#define MOD (1000000007)#define PI acos(-1.0)#define DINF (1e10)#define LINF ((1LL)<<50)#define INF (0x3f3f3f3f)#define max(a,b) ((a) > (b) ? (a) : (b))#define min(a,b) ((a) < (b) ? (a) : (b))#define max3(a,b,c) (max(max(a,b),c))#define min3(a,b,c) (min(min(a,b),c))#define BUG cout<<"BUG! "< > 1)#define lowbit(a) (a & -a)#define FIN freopen("in.txt","r",stdin)#define FOUT freopen("out.txt","w",stdout)#pragma comment (linker,"/STACK:102400000,102400000")// typedef long long LL;// typedef unsigned long long ULL;typedef __int64 LL;// typedef unisigned __int64 ULL;// LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; }// LL lcm(LL a,LL b){ return a*b/gcd(a,b); }/********************* F ************************/int size = 5; // can be dynamicstruct matrix{ LL ma[MAXN][MAXN]; matrix(){memset(ma,0,sizeof(ma));} matrix operator + (const matrix &a)const { matrix t; for(int i = 0; i < size ; i++) for(int j = 0; j < size ; j++) t.ma[i][j] = (ma[i][j] + a.ma[i][j]) % MOD; return t; } matrix operator * (const matrix &a)const { matrix t; for(int i = 0 ; i < size ; i++) for(int j = 0 ; j < size ; j++) for(int k = 0 ; k < size ; k++) t.ma[i][j] = (t.ma[i][j] + (ma[i][k] * a.ma[k][j]) % MOD) % MOD ; return t; } matrix operator ^ (const LL &n)const { matrix p = *this; if(n == 1) return p; matrix t = p ^ (n/2); if(n & 1) return t * t * p; else return t * t; } void show(){ for(int i = 0 ; i < size ; i++){ for(int j = 0 ; j < size ; j++) printf("%6lld ",ma[i][j]); puts(""); } }};int main(){ LL N,A0,AX,AY,B0,BX,BY; while(~scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&N,&A0,&AX,&AY,&B0,&BX,&BY)){ A0 = A0 % MOD; AX = AX % MOD; AY = AY % MOD; B0 = B0 % MOD; BX = BX % MOD; BY = BY % MOD; if(N == 0) { printf("0\n"); continue; } if(N == 1) { printf("%I64d\n",(A0*B0)%MOD); continue; } matrix ori; ori.ma[0][0] = AX; ori.ma[1][1] = BX; ori.ma[0][4] = AY; ori.ma[1][4] = BY; ori.ma[3][3] = ori.ma[4][4] = 1; ori.ma[2][0] = ori.ma[3][0] = (BY * AX) % MOD; ori.ma[2][1] = ori.ma[3][1] = (BX * AY) % MOD; ori.ma[2][2] = ori.ma[3][2] = (BX * AX) % MOD; ori.ma[2][4] = ori.ma[3][4] = (BY * AY) % MOD; matrix t = ori ^ (N-1); LL ans = (t.ma[3][0] * A0) % MOD; ans = (ans + (t.ma[3][1] * B0) % MOD) % MOD; ans = (ans + (t.ma[3][2] * ((A0 * B0) % MOD)) % MOD) % MOD; ans = (ans + (A0 * B0) % MOD) % MOD; ans = (ans + t.ma[3][4]) % MOD; printf("%I64d\n",ans); } return 0;}
转载于:https://www.cnblogs.com/Felix-F/p/3272769.html