cf 1182 E - Product Oriented Recurrence

当时脑残了，不会写矩阵快速幂中更改的系数，其实把他扔到矩阵里同时递推就好了
#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

using namespace std;

ll read() {

	ll nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

const int mod = 1000000006, mod1 = 1000000007;

void add(int &x, int y) {

	x += y;

	x -= x >= mod ? mod : 0;

}

int mul(int a, int b) {

	return 1ll * a * b % mod;

}

void add1(int &x, int y) {

	x += y;

	x -= x >= mod ? mod : 0;

}

int mul1(int a, int b) {

	return 1ll * a * b % mod1;

}

struct Note {

	int a[5][5], h, l;

	Note() {

		memset(a, 0, sizeof(a));

		h = l = 0;

	}

	void init() {

		memset(a, 0, sizeof(a));

		h = l = 0;

	}

} be, ed, tmp, biao;

Note operator * (Note a, Note b) {

	Note c;

	c.h = a.h, c.l = b.l;

	for(int i = 0; i < a.h; i++) {

		for(int j = 0; j < a.l; j++) {

			for(int k = 0; k < b.l; k++) {

				add(c.a[i][k], mul(a.a[i][j], b.a[j][k]));

			}

		}

	}

	return c;

}

int poww(int a, int b) {

	int ans = 1, tmp = a;

	for(; b; b >>= 1, tmp = mul1(tmp, tmp)) if(b & 1) ans = mul1(ans, tmp);

	return ans;

}

Note poww(ll x) {

	tmp = biao;

	for(; x; x >>= 1, tmp = tmp *  tmp) if(x & 1) be = be * tmp;

	return be;

}

int f1, f2, f3, c, ans = 1;

ll n;

void init() {

	be.init();

	biao.init();

}

int main() {

	n = read();

	n -= 3;

	f1 = read(), f2 = read(), f3 = read(), c = read();

	init();

	be.h = 1, be.l = 3;

	be.a[0][0] = 1;

	biao.h = biao.l = 3;

	biao.a[0][2] = biao.a[1][0] = biao.a[1][2] = biao.a[2][1] = biao.a[2][2] = 1;

	ed = poww(n);

	ans = mul1(ans, poww(f1, ed.a[0][2]));

	init();

	be.h = 1, be.l = 3;

	be.a[0][1] = 1;

	biao.h = biao.l = 3;

	biao.a[0][2] = biao.a[1][0] = biao.a[1][2] = biao.a[2][1] = biao.a[2][2] = 1;

	ed = poww(n);

	ans = mul1(ans, poww(f2, ed.a[0][2]));

	init();

	be.h = 1, be.l = 3;

	be.a[0][2] = 1;

	biao.h = biao.l = 3;

	biao.a[0][2] = biao.a[1][0] = biao.a[1][2] = biao.a[2][1] = biao.a[2][2] = 1;

	ed = poww(n);

	ans = mul1(ans, poww(f3, ed.a[0][2]));

	init();

	be.h = 1, be.l = 5;

	be.a[0][3] = 8, be.a[0][4] = 1;

	biao.h = biao.l = 5;

	biao.a[4][4] = biao.a[1][0] = biao.a[0][2] = biao.a[1][2] = biao.a[2][1] = biao.a[2][2] = biao.a[3][2] = biao.a[3][3] = 1;

	biao.a[4][2] = mod - 6;

	biao.a[4][3] = 2;

	ed = poww(n);

	ans = mul1(ans, poww(c, ed.a[0][2]));

	cout << ans << "\n";

	return 0;

}
巴特西

cf 1182 E - Product Oriented Recurrence

最新文章

热门文章
