1.題目鏈接。構(gòu)造g(x)=f(x)*c^x.然后發(fā)現(xiàn):g(x)=g(x-1)*g(x-2)*g(x-3).一種類似與線性遞推的東西，這個(gè)時(shí)候，指數(shù)是可以線性遞推的。也就是g(x)=g(3)^(a(x)*g(2)^(b(x)*g(1)^(c(x)).其中指數(shù),a(x),b(x),c(x)互相獨(dú)立，并且滿足遞推：a(x)=a(x-1)+a(x-2)+a(x-3),b,c也是如此。然后矩陣快速冪求出指數(shù)，指數(shù)取模后求g(x),最后求個(gè)c^(x)對(duì)1e9+7的逆元完事。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; #pragma warning(disable:4996) struct Sarray {static const ll mod = 1e9 + 6;static const ll LEN = 3;ll len, data[LEN][LEN];Sarray(ll len, ll flag) :len(len) {for (ll i = 0; i < len; i++) {for (ll j = 0; j < len; j++)data[i][j] = 0;data[i][i] = flag;}}Sarray operator *(const Sarray&a) {Sarray tem(a.len, 0);for (ll i = 0; i < len; i++) {for (ll j = 0; j < len; j++) {for (ll k = 0; k < len; k++) {tem.data[i][j] = (tem.data[i][j] + data[i][k] * a.data[k][j]) % mod;}}}return tem;}Sarray operator +(const Sarray&a) {Sarray tem(a.len, 0);for (ll i = 0; i < len; i++) {for (ll j = 0; j < len; j++) {tem.data[i][j] = (data[i][j] + a.data[i][j]) % mod;}}return tem;} };Sarray qpow(Sarray a, ll b) {Sarray tem(a.len, 1);while (b) {if (b & 1)tem = a * tem;a = a * a;b >>= 1;}return tem; }ll qpow(ll a, ll b) {ll ret = 1;while (b) {if (b & 1) ret = ret * a%mod;a = a * a%mod;b >>= 1;}return ret; } ll inita[3][3] = {0,0,0,0,0,0,1,0,0 };ll initb[3][3] = {0,0,0,1,0,0,0,0,0 }; ll initc[3][3] = {1,0,0,0,0,0,0,0,0 }; ll trans[3][3] = {1,1,1,1,0,0,0,1,0 };ll getPon(ll n, ll beg[3][3]) {Sarray orn(3, 1), trans1(3, 1);memcpy(orn.data, beg, sizeof(orn.data));memcpy(trans1.data, trans, sizeof(trans1.data));if (n == 1) return beg[2][0];if (n == 2) return beg[1][0];return (qpow(trans1, n - 3)*orn).data[0][0]; } int main() {ll n, f1, f2, f3, c;while (cin >> n >> f1 >> f2 >> f3 >> c){ll g1 = f1 * c%mod;ll g2 = f2 * c%mod*c%mod;ll g3 = f3 * c%mod*c%mod*c%mod;ll ponmod = mod - 1;//指數(shù)取模ll A = getPon(n, inita)%ponmod;ll B = getPon(n, initb)%ponmod;ll C = getPon(n, initc)%ponmod;ll gn = qpow(g1, A)*qpow(g2, B) % mod*qpow(g3, C) % mod;//找一下逆元ll cn = qpow(c, n);ll inv = qpow(cn, mod - 2);ll ans = gn * inv%mod;cout << ans << endl;} }

?

總結(jié)

以上是生活随笔為你收集整理的【cf 1182 E】Product Oriented Recurrence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。