牛客国庆集训day5 B 电音之王（大数乘模）

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

题目描述

终于活成了自己讨厌的样子。
听说多听电音能加快程序运行的速度。
定义一个数列，告诉你a₀,a₁,m₀,m₁,c，定义a_n=m₀a_n-1+m₁a_n-2+c对所有n≥ 2。
求 $\left( \prod_{i=0}^k a_i \right) \bmod M$

输入描述:

第一行一个整数T(1≤ T≤ 1000)，表示数据组数。
每组数据一行7个整数a

₀

,a

₁

,m

₀

,m

₁

,c,M,k，保证1≤ M≤ 10

¹⁸

,0≤ a

₀

,a

₁

,m

₀

,m

₁

,c< M, 2≤ k≤ 10

⁶

，保证M为奇数。
保证

$\sum k \leq 10^8$

。

输出描述:

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

示例1

输入

复制

1
1 1 1 1 0 1000000007 10

输出

复制

904493530



蒙哥马利板子题。

 1 #include <bits/stdc++.h>
 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

牛客国庆集训day5 B 电音之王 （大数乘模）

题目描述

输入描述:

输出描述:

输入

输出

牛客国庆集训day5 B 电音之王（大数乘模）