链接：https://www.nowcoder.com/acm/contest/205/B
来源：牛客网

题目描述

终于活成了自己讨厌的样子。
听说多听电音能加快程序运行的速度。
定义一个数列，告诉你a0,a1,m0,m1,c，定义an=m0an-1+m1an-2+c对所有n≥ 2。
求

输入描述:

第一行一个整数T(1≤ T≤ 1000)，表示数据组数。
每组数据一行7个整数a 0,a 1,m 0,m 1,c,M,k，保证1≤ M≤ 10 18,0≤ a 0,a 1,m 0,m 1,c< M, 2≤ k≤ 10 6，保证M为奇数。
保证 。

输出描述:

对于每组数据，输出一行表示答案。 示例1

输入

复制 1 1 1 1 1 0 1000000007 10

输出

复制 904493530



蒙哥马利板子题。



1 #include 2 using namespace std; 3 4 typedef long long ll; 5 typedef unsigned long long u64; 6 typedef __int128_t i128; 7 typedef __uint128_t u128; 8 9 struct Mod64 { 10 Mod64() :n_(0) {} 11 Mod64(u64 n) :n_(init(n)) {} 12 static u64 init(u64 w) { return reduce(u128(w) * r2); } 13 static void set_mod(u64 m) { 14 mod = m; assert(mod & 1); 15 inv = m; for (int i = 0; i < 5; ++i) inv *= 2 - inv * m; 16 r2 = -u128(m) % m; 17 } 18 static u64 reduce(u128 x) { 19 u64 y = u64(x >> 64) - u64((u128(u64(x)*inv)*mod) >> 64); 20 return ll(y)<0 ? y + mod : y; 21 } 22 Mod64& operator += (Mod64 rhs) { n_ += rhs.n_ - mod; if (ll(n_)<0) n_ += mod; return *this; } 23 Mod64 operator + (Mod64 rhs) const { return Mod64(*this) += rhs; } 24 Mod64& operator -= (Mod64 rhs) { n_ -= rhs.n_; if (ll(n_)<0) n_ += mod; return *this; } 25 Mod64 operator - (Mod64 rhs) const { return Mod64(*this) -= rhs; } 26 Mod64& operator *= (Mod64 rhs) { n_ = reduce(u128(n_)*rhs.n_); return *this; } 27 Mod64 operator * (Mod64 rhs) const { return Mod64(*this) *= rhs; } 28 u64 get() const { return reduce(n_); } 29 static u64 mod, inv, r2; 30 u64 n_; 31 }; 32 33 u64 Mod64::mod, Mod64::inv, Mod64::r2; 34 35 36 int t, k; 37 u64 A0, A1, M0, M1, C, M; 38 39 void Run() 40 { 41 scanf("%d", &t); 42 while (t--) 43 { 44 scanf("%llu%llu%llu%llu%llu%llu%d", &A0, &A1, &M0, &M1, &C, &M, &k); 45 Mod64::set_mod(M); 46 Mod64 a0(A0), a1(A1), m0(M0), m1(M1), c(C), ans(1), a2(0); 47 ans *= a0; ans *= a1; 48 for (int i = 2; i <= k; ++i) 49 { 50 a2 = a1; 51 a1 = m0 * a1 + m1 * a0 + c; 52 a0 = a2; 53 ans *= a1; 54 } 55 printf("%llu ", ans.get()); 56 } 57 } 58 59 int main() 60 { 61 Run(); 62 return 0; 63 } View Code