HDU 4686 Arc of Dream（构造矩阵）

设\(t_n=a_n*b_n\)
把\(a_n 和b_n\)拆出来
\(t_n=(a_{n-1}*ax+ay)(b_{n-1}*bx+by)\)
\(t_n=ax*bx*t_{n-1}+ax*by*a_{n}+ay*bx*b_{n-1}+ay*by\)
那么同时维护\(s_n, t_n, a_n, b_n 和常数即可\)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
//#define A puts("Yes")
//#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const ll inf = 1ll << 60;
const ll mo=1000000007;
ll n,a[N],ax,ay,b[N],bx,by;
struct mat{
	ll a[13][13];
	void init() {
		memset(a,0,sizeof(a));
	}
	friend mat operator * (const mat &a,const mat &b) {
		mat c;
		c.init();
		fo(i,1,5) fo(j,1,5) fo(k,1,5) {
			c.a[i][j]+=a.a[i][k]*b.a[k][j]%mo;
			c.a[i][j]%=mo;
		}
		return c;
	}
	void print(){
		fo(i,1,5) {
			fo(j,1,5) printf("%lld ",a[i][j]);
			printf("\n");
		}
	}
}; 

void solve(){
	scanf("%lld %lld %lld",&a[0], &ax,&ay);
	scanf("%lld %lld %lld",&b[0], &bx,&by);
	
	if (!n) {
		printf("%d\n",0);
		return;
	}
	a[0]%=mo;
	b[0]%=mo;
	ax%=mo;
	ay%=mo;
	bx%=mo;
	by%=mo;
	
	mat t,y;
	t.init();
	y.init();
	
	t.a[1][1]=a[0]*b[0]%mo;
	t.a[2][1]=a[0]*b[0]%mo;
	t.a[3][1]=a[0];
	t.a[4][1]=b[0];
	t.a[5][1]=1;
	
	y.a[1][1]=1; y.a[1][2]=ax*bx%mo; y.a[1][3]=ax*by%mo; y.a[1][4]=ay*bx%mo; y.a[1][5]=ay*by%mo;
	fo(i,2,5) y.a[2][i]=y.a[1][i];
	
	y.a[3][3]=ax; y.a[3][5]=ay;
	y.a[4][4]=bx; y.a[4][5]=by;
	y.a[5][5]=1;
	
//	y.print();

	n--;
	while (n) {
		if (n&1) t=y*t;
		y=y*y;
		n/=2;
	}
	
	printf("%lld\n",t.a[1][1]);
}
int main()
{
//	freopen("data.in","r",stdin);
	
	while (scanf("%lld",&n)!=EOF) {
		solve();
	}
	
	return 0;
}