Pixiv - Miracle
3-牛客挑战赛 87题解
482 字
2 分钟
3-牛客挑战赛 87题解
链接：https://ac.nowcoder.com/acm/contest/130844/C 来源：牛客网
题目描述
Papy 是出题组唯一的高中生，CirnoNine 为了欺负 Papy，给了他一道高中数学经典的等差乘等比的数列求和式：
由于这个答案可能很大，CirnoNine 只要求 Papy 回答 即可。
输入描述:
每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：
第一行输入四个整数 ，含义如题。
第二行输入一个二进制整数 ，保证 不存在前导 ，含义如题。
除此之外，保证单个测试文件的二进制整数的长度之和（即 之和）不超过 。
输出描述:
对于每一组测试数据，新起一行输出一个整数表示 。
矩阵快速幂
#include <bits/stdc++.h>using namespace std;using ll = long long;
void solve() { ll MOD, a, b, q; string n; cin >> MOD >> a >> b >> q; cin >> n;
ll p = 1 % MOD; // q^0 ll g = 0; // sum q^i ll h = 0; // sum i*q^i ll x = 0; // 当前前缀对应的值 mod MOD
for (char c : n) { ll p2 = p * p % MOD; ll g2 = g * ((1 + p) % MOD) % MOD; ll h2 = (h * ((1 + p) % MOD) % MOD + p * x % MOD * g % MOD) % MOD; ll x2 = x * 2 % MOD;
if (c == '1') { p2 = p2 * q % MOD; g2 = (g2 + p2) % MOD; h2 = (h2 + (x2 + 1) % MOD * p2) % MOD; x2 = (x2 + 1) % MOD; }
p = p2; g = g2; h = h2; x = x2; }
cout << (a % MOD * h % MOD + b % MOD * g % MOD) % MOD << '\n';}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T; while (T--) solve();}文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
3-牛客挑战赛 87题解
https://skaco2.com/posts/03-solutions/3-牛客挑战赛-87题解/ 随机文章 随机推荐