OI笔记 | 2022.11 做题记录（三）
还有不到一周 NOIP，别想太多，好好复习，然后 rp++。
- Z
- 低价购买
- [SCOI2010] 序列操作
- [USACO10MAR] Great Cow Gathering G
- Fibonacci
- K皇后
- MatryoshkaDoll
- [JRKSJ R5] 1-1 B
- [NOIP2020] 排水系统
- Story
Z
给定正整数 $n$，你要构造两个正整数 $x,y$，满足：
\[1\le x,y\le 10^{18}\] \[x-y=n\] \[\omega(x)=\omega(y)\]其中 $\omega(m)$ 表示能整除 $m$ 的素数个数，比如 $\omega(12)=2$，因为 $2\mid12$ 且 $3\mid12$。再比如 $\omega(998244353)=1$，因为 $998244353$ 是质数。
数据范围保证存在至少一组满足条件的 $x,y$。
$T\le10^4,n\le 10^9$
题解
对于偶数 $n$，构造 $x=2n,y=n$ 即可。显然 $x$ 和 $y$ 的质因数个数相同。
对于奇数 $n$，构造 $x=pn,y=(p-1)n$ 即可，其中 $p$ 为满足 $p\nmid n$ 且 $p\ne 2$ 的最小质数。这会让：
$\omega(pn)$ 比 $\omega(n)$ 多 $1$，即多了 $p$ 这个质数。
$\omega[(p-1)n]$ 的也比 $\omega(n)$ 多 $1$，即由于 $(p-1)$ 一定为偶数，所以多了 $2$ 这个质数。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6;
vector<ll> primes;
bool vis[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline void init() {
for(int i = 2; i < MAX_N; i++) {
if(!vis[i]) primes.push_back(i);
for(int k = 0; k < primes.size() && primes[k] * i < MAX_N; k++) {
vis[primes[k] * i] = 1;
if(i % primes[k] == 0) break;
}
}
}
int main() {
init();
ll T = read();
while(T--) {
ll n = read();
if(n % 2 == 0) {
write(2 * n), putchar(' ');
write(n), putchar('\n');
}
else {
ll p = 1;
for(int i = 1; i < primes.size(); i++) {
if(n % primes[i] != 0) {
p = primes[i];
break;
}
}
write(p * n), putchar(' ');
write((p - 1) * n), putchar('\n');
}
}
return 0;
}
低价购买
求最长下降子序列的长度，以及达到该长度的最长下降子序列数。
题解
见注释。参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e3 + 10;
int dp[MAX_N], a[MAX_N], l[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), ans = 0, t = 0;
for(int i = 1; i <= n; i++) {
a[i] = read(), dp[i] = 1;
for(int j = 1; j < i; j++) if(a[i] < a[j]) dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
if(dp[i] == 1) l[i] = 1;
for(int j = 1; j < i; j++) {
if(dp[i] == dp[j] + 1 && a[i] < a[j]) l[i] += l[j]; // 如果 dp 时是由 j 接上的，那么方案数从 j 累加过来
else if(dp[i] == dp[j] && a[i] == a[j]) l[j] = 0; // 如果 i 和 j 结尾的序列长度相同，值也相同，那么是相同的序列，会被重复计算，所以将 l[j] 和 l[i] 中的随意一个变成 0 即可
}
}
for(int i = 1; i <= n; i++) if(dp[i] == ans) t += l[i]; // l[i] 是方案数
write(ans), putchar(' '), write(t);
return 0;
}
[SCOI2010] 序列操作
给定一个 $01$ 序列，序列里面包含了 $n$ 个数，下标从 $0$ 开始。这些数要么是 $0$，要么是 $1$，现在对于这个序列有五种变换操作和询问操作：
-
0 l r把 $[l, r]$ 区间内的所有数全变成 $0$ -
1 l r把 $[l, r]$ 区间内的所有数全变成 $1$ -
2 l r把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$，把所有的 $1$ 变成 $0$ -
3 l r询问 $[l, r]$ 区间内总共有多少个 $1$ -
4 l r询问 $[l, r]$ 区间内最多有多少个连续的 $1$
$1\le n,m \le 10^5$。
题解
有点复杂的线段树，不太会写，于是照着小粉兔的题解写，不过码风是自己的码风。
以后多练练这种需要储存很多信息的线段树。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
bool a[MAX_N];
int tag1[MAX_N << 2], tag2[MAX_N << 2], len[MAX_N << 2];
struct node {
int T, F, Tlmax, Flmax, Trmax, Frmax, Tmax, Fmax;
} d[MAX_N << 2];
inline ll read() {...}
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline node U(node x, node y) {
node ret;
ret.T = x.T + y.T, ret.F = x.F + y.F;
if(x.F) ret.Tlmax = x.Tlmax;
else ret.Tlmax = x.T + y.Tlmax;
if(x.T) ret.Flmax = x.Flmax;
else ret.Flmax = x.F + y.Flmax;
if(y.F) ret.Trmax = y.Trmax;
else ret.Trmax = y.T + x.Trmax;
if(y.T) ret.Frmax = y.Frmax;
else ret.Frmax = y.F + x.Frmax;
ret.Tmax = max(max(x.Tmax, y.Tmax), x.Trmax + y.Tlmax);
ret.Fmax = max(max(x.Fmax, y.Fmax), x.Frmax + y.Flmax);
return ret;
}
inline void change(int p, int type) {
if(type == 0) {
tag2[p] = tag1[p] = 0;
d[p].T = d[p].Tlmax = d[p].Trmax = d[p].Tmax = 0;
d[p].F = d[p].Flmax = d[p].Frmax = d[p].Fmax = len[p];
}
else if(type == 1) {
tag2[p] = 0, tag1[p] = 1;
d[p].T = d[p].Tlmax = d[p].Trmax = d[p].Tmax = len[p];
d[p].F = d[p].Flmax = d[p].Frmax = d[p].Fmax = 0;
}
else if(type == 2) {
tag2[p] ^= 1;
swap(d[p].T, d[p].F);
swap(d[p].Tlmax, d[p].Flmax);
swap(d[p].Trmax, d[p].Frmax);
swap(d[p].Tmax, d[p].Fmax);
}
}
inline void pu(int p) {d[p] = U(d[lc(p)], d[rc(p)]);}
inline void pd(int p) {
if(tag1[p] != -1) change(lc(p), tag1[p]), change(rc(p), tag1[p]);
if(tag2[p]) change(lc(p), 2), change(rc(p), 2);
tag1[p] = -1, tag2[p] = 0;
}
void build_tree(int s, int t, int p) {
len[p] = t - s + 1, tag1[p] = -1;
if(s == t) {
d[p].T = d[p].Tlmax = d[p].Trmax = d[p].Tmax = a[s];
d[p].F = d[p].Flmax = d[p].Frmax = d[p].Fmax = (a[s] ^ 1);
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
void update(int s, int t, int l, int r, int p, int type) {
if(r < s || l > t) return;
if(l <= s && t <= r) {change(p, type); return;}
pd(p);
int m = mid(s, t);
update(s, m, l, r, lc(p), type);
update(m + 1, t, l, r, rc(p), type);
pu(p);
}
node query(int s, int t, int l, int r, int p) {
if(r < s || l > t) return (node){0, 0, 0, 0, 0, 0, 0, 0};
if(l <= s && t <= r) return d[p];
pd(p);
int m = mid(s, t);
return U(query(s, m, l, r, lc(p)), query(m + 1, t, l, r, rc(p)));
}
int main() {
int n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
build_tree(1, n, 1);
while(m--) {
int op = read(), l = read() + 1, r = read() + 1;
if(op < 3) update(1, n, l, r, 1, op);
else {
node ret = query(1, n, l, r, 1);
if(op == 3) write(ret.T);
else write(ret.Tmax);
putchar('\n');
}
}
return 0;
}
[USACO10MAR] Great Cow Gathering G
给出一个既有点权又有边权的树，求出它的重心到所有点的距离之和。
题解
洛谷 P1364 这题是有点权无边权的相同题目；洛谷 P1395 这题是无点权无边权的相同题目。其实做法都差不多：它们都有一个 $O(n)$ 的 dp 做法。
不妨钦定 $1$ 为树的根。我们用 $c_i$ 表示 $i$ 的点权， $dep_i$ 表示从 $1$ 到 $i$ 的距离， $siz_i$ 表示以 $i$ 为根的子树的大小。另外，用 $f_i$ 表示 $i$ 到所有点的距离之和，所以答案为 $\min\limits_{i=1}^n f_i$。
显然我们 dfs 一遍就能求出所有的 $dep_i$ 与 $siz_i$。从而我们知道 $f_1=\sum\limits_{i=1}^n (dep_i \cdot c_i)$。
考虑边 $(u,v,w)$，显然 $f_v$ 可以由 $f_u$ 转移过来。具体来说，不在 $v$ 子树里的 $(siz_1-siz_v)$ 大小的点到 $v$ 的距离都增加了 $w$；在 $v$ 子树里的 $siz_v$ 大小的点到 $v$ 的距离都减少了 $w$。合并一下，所以转移方程为：
\[f_v = f_u + siz_1\cdot w - 2\cdot siz_v\cdot w\]参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
ll c[MAX_N], siz[MAX_N], dep[MAX_N], f[MAX_N], dp[MAX_N], ans;
struct edge {int u, v, w;};
vector<edge> edges;
vector<int> G[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline void AddEdge(int u, int v, int w) {
edges.push_back({u, v, w});
G[u].push_back(edges.size() - 1);
}
void dfs1(int u, int fa) {
siz[u] = c[u];
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;
if(v == fa) continue;
dep[v] = dep[u] + w;
dfs1(v, u);
siz[u] += siz[v];
}
}
void dfs2(int u, int fa) {
for(int i = 0; i < G[u].size(); i++) {
int v = edges[G[u][i]].v, w = edges[G[u][i]].w;
if(v == fa) continue;
f[v] = f[u] + siz[1] * w - 2 * siz[v] * w;
ans = min(ans, f[v]);
dfs2(v, u);
}
}
int main() {
int n = read();
for(int i = 1; i <= n; i++) c[i] = read();
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w), AddEdge(v, u, w);
}
dfs1(1, 0);
for(int i = 1; i <= n; i++) f[1] += dep[i] * c[i];
ans = f[1];
dfs2(1, 0);
write(ans);
return 0;
}
Fibonacci
给定长为 $n$ 的序列 $c$，求它的最长斐波那契子序列的长度。
定义斐波那契序列为满足 $\forall\ 3\le i\le t,a_i=a_{i-1}+a_{i-2}$ 的序列，其中 $t$ 为序列的长度。
题解
用 $dp_{m,n}$ 表示以 $a_m,a_n$ 为第 $1$ 项和第 $2$ 项的最长斐波那契子序列的长度。考虑从后向前进行转移，则转移方程为：
\[dp_{j,i}=dp_{i,k}+1\]转移的条件为 $a_k=a_j+a_i$ 且 $1\le j<i<k\le n$。
考虑用 hash 表来快速找到满足条件的 $k$。同时由于倒序枚举，可以在枚举到 $i$ 的时候再赋值 $idx_{a_i}=i$，这样 $k$ 自然会满足 $k>i$。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 3010;
int a[MAX_N], dp[MAX_N][MAX_N], ans;
unordered_map<int, int> idx;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = n; i > 1; i--) {
for(int j = 1; j < i; j++) {
if(idx.count(a[i] + a[j])) {
int k = idx[a[i] + a[j]];
dp[j][i] = dp[i][k] + 1;
ans = max(ans, dp[j][i] + 2);
}
}
idx[a[i]] = i;
}
write(ans);
return 0;
}
K皇后
小 Z 最近捡到了一个棋盘，他想在棋盘上摆放 $K$ 个皇后。他想知道在他摆完这 $K$ 个皇后之后，棋盘上还有多少个格子是不会被攻击到的。
注意：一个皇后会攻击到这个皇后所在的那一行，那一列，以及两条对角线。
$1\le n,m\le 2\times 10^4$，$1\le K\le 500$。
题解
枚举行，然后判断这个行能放多少皇后。
时间复杂度：$O(n(m+k))$。其中乘上 $m$ 是因为要清空 $f$ 标记数组与统计答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e4 + 10;
pii q[MAX_N];
bool vis[MAX_N], f[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read(), k = read(), ans = 0;
for(int i = 1; i <= k; i++) {
q[i].first = read();
q[i].second = read();
vis[q[i].first] = 1;
}
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
for(int j = 1; j <= m; j++) f[j] = 0;
for(int j = 1; j <= k; j++) {
int x = q[j].first, y = q[j].second;
f[y] = 1;
int ty1 = y - abs(x - i), ty2 = y + abs(x - i);
if(ty1 >= 1) f[ty1] = 1;
if(ty2 <= m) f[ty2] = 1;
}
for(int j = 1; j <= m; j++) ans += (f[j] == 0);
}
write(ans);
return 0;
}
MatryoshkaDoll
给出 $n$ 个套娃的大小 $a_1,a_2,\dots, a_n$。给定 $k$，你要把这 $n$ 个套娃分成 $k$ 组，使得每一组都能嵌套。求出方案数 $(\bmod \ 998244353)$ 。
一个组 $c_1,c_2,\dots c_t$ 嵌套指的是 $\forall\ 1 \le i < t,\ a_{c_i}+r\le a_{c_{i+1}}$，其中 $r$ 是给定的常数。
多组数据，$1\le T\le20,\sum n\le 50000$。对于每组数据，有 $1\le k\le n\le 5000, 1\le a_1\le \dots \le a_n \le 10^9,1\le r\le10^9$。
题解
考虑 dp，类比子集划分（第二类斯特林数），我们用 $dp_{i,j}$ 表示把前 $i$ 个数分成 $j$ 组的方案数。如果不考虑能否嵌套，转移方程即为：
\[dp_{i,j}=dp_{i-1,j-1}+j\cdot dp_{i-1,j}\]边界条件为 $dp_{i,i}=1$。
这是因为我们既可以把第 $i$ 个单独分成新的一组( $dp_{i-1,j-1}$ )，也可以把它分到原来 $j$ 组的任意一个去( $j\cdot dp_{i-1,j}$ )，然后根据加法原理，$dp_{i,j}$ 就是这两种情况方案数之和。
对于这题，唯一的区别就是不能分到前 $j$ 组的任意一个去，要减掉不满足嵌套条件的组数。如果暴力枚举当前状态有多少不满足的组数，时间复杂度是 $O(n^3T)$ 的，但我们需要 $O(n^2 T)$。
所以考虑预处理。用 $f_i$ 表示前 $i-1$ 个元素组成的组中不满足嵌套条件的组数，容易发现不论分成几组，$f_i$ 是唯一的，它等于 $[1,i-1]$ 中满足 $a_j+r>a_i$ 的 $j$ 的个数。证明：考虑 $a$ 的递增性质，如果 $a_j+r>a_i$，它必然是所在组别的最大值（因为满足条件的 $j$ 不可能分在同一组），也就必然导致这一组不能与 $i$ 嵌套。
于是转移方程为：
\[dp_{i,j}=dp_{i-1,j-1}+(j-f_i)\cdot dp_{i-1,j}\]参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_N = 5e3 + 10, MOD = 998244353;
ll dp[MAX_N][MAX_N], a[MAX_N], f[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int T = read();
while(T--) {
ll n = read(), k = read(), r = read();
for(ll i = 1; i <= n; i++) {
a[i] = read();
dp[i][i] = 1, f[i] = 0;
for(ll j = 1; j < i; j++) f[i] += (a[j] + r > a[i]);
}
for(ll i = 1; i <= n; i++) {
for(ll j = 1; j < i; j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * (j - f[i]);
dp[i][j] %= MOD;
}
}
write(dp[n][k]), putchar('\n');
}
return 0;
}
[JRKSJ R5] 1-1 B
给出一个序列 $a$，$\forall i\in [1,n],a_i\in {1,-1}$。
询问有多少个将 $a$ 重排后的序列使得该序列的最大子段和最小化。
称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。
答案对 $998244353$ 取模。
$1\le n\le 10^4$，$a_i\in {1,-1}$。
题解
显然答案只与 $1/0$ 的数量有关。设 $1$ 的数量为 $cnt_1$， $-1$ 的数量为 $cnt_2$，那么分两类：
-
若 $cnt_1\le cnt_2$，最小的最大子段和必然是 $1$。所以方案数就是把原序列进行排列，使得任意两个 $1$ 不相邻的方案数。参考 oi-wiki 上的页面，答案就等于 $\binom{n-cnt_1+1}{cnt_1}$ 也就是 $\binom{cnt_2+1}{cnt_1}$。$O(n)$ 预处理阶乘求组合数即可。
-
若 $cnt_1>cnt_2$，最小的最大子段和必然是 $cnt_1-cnt_2$，也就是把所有数都加起来。考虑设计 $dp_{i,j}$ 为考虑前 $i$ 个数中有 $j$ 个为 $1$ 的方案数。那么转移就是：第 $i$ 位取 $1$ 的方案数等于 $dp_{i-1,j-1}$，取 $-1$ 的方案数为 $dp_{i-1,j}$，加起来即可。转移条件就是 $0\le sum_i\le sum_n$，其中 $sum_i$ 为前缀和。前缀和小于 $0$ 那么方案数显然应该是 $0$。注意到交上去会 MLE，所以滚动数组优化一下。
参考代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e4 + 10, MOD = 998244353;
int dp[2][MAX_N], fac[MAX_N];
inline ll read() {...}
inline void write(ll x) {...}
inline void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {x = 1, y = 0; return;}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline ll inv(ll v) {
ll x, y;
exgcd(v, MOD, x, y);
return (x % MOD + MOD) % MOD;
}
int main() {
int n = read(), sum = 0, cnt1 = 0, cnt2 = 0;
for(int i = 1; i <= n; i++) {
int x = read();
if(x == 1) cnt1++;
else cnt2++;
sum += x;
}
if(cnt1 <= cnt2) {
fac[0] = fac[1] = 1;
for(int i = 2; i <= n + 1; i++) fac[i] = (1ll * fac[i - 1] * i) % MOD;
ll ans = 1ll * fac[cnt2 + 1] * inv(fac[cnt1]) % MOD * inv(fac[cnt2 - cnt1 + 1]) % MOD;
write(ans);
}
else {
dp[0][0] = 1;
bool now = 0;
for(int i = 1; i <= n; i++) {
now ^= 1;
for(int j = 1; j <= min(cnt1, i); j++) {
int s = 2 * j - i;
if(s >= 0 && s <= sum) dp[now][j] = (dp[now ^ 1][j - 1] + dp[now ^ 1][j]) % MOD;
else dp[now][j] = 0;
}
}
write(dp[now][cnt1]);
}
return 0;
}
[NOIP2020] 排水系统
对于一个城市来说，排水系统是极其重要的一个部分。
有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 $n$ 个排水结点（它们从 $1 \sim n$ 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。
排水系统的结点中有 $m$ 个污水接收口，它们的编号分别为 $1, 2, \ldots , m$，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。
现在各个污水接收口分别都接收了 $1$ 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。
现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。
$1 \le n \le {10}^5$，$1 \le m \le 10$，$0 \le d_i \le 5$。
题解
大概是拓扑排序的板题。然后用 __int128 就不用写高精了，方便分数用 gcd 化简。
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int MAX_N = 1e5 + 10;
vector<int> G[MAX_N], ans;
int in[MAX_N], n, m;
inline ll read() {...}
inline void write(ll x) {...}
inline ll gcd(ll m, ll n) {while(n != 0) {ll t = m % n; m = n, n = t;} return m;}
inline ll lcm(ll m, ll n) {return m * n / gcd(m, n);}
struct frac {
ll a, b;
frac() {a = 0, b = 1;}
void reduce() {
ll d = gcd(a, b);
a /= d, b /= d;
}
void print() {
write(a), putchar(' ');
write(b), putchar('\n');
}
frac operator + (const frac &t) const {
frac ret;
ret.b = lcm(b, t.b);
ret.a = ret.b / b * a + ret.b / t.b * t.a;
ret.reduce();
return ret;
}
} w[MAX_N];
void topo() {
queue<int> q;
for(int i = 1; i <= n; i++) if(in[i] == 0) q.push(i), w[i].a = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
int out = G[u].size();
if(out > 0) {
w[u].b *= out;
for(int i = 0; i < out; i++) {
int v = G[u][i];
w[v] = w[v] + w[u];
if(--in[v] == 0) q.push(v);
}
}
}
}
int main() {
n = read(), m = read();
for(int u = 1; u <= n; u++) {
int d = read();
for(int i = 1; i <= d; i++) {
int v = read();
G[u].push_back(v);
in[v]++;
}
if(d == 0) ans.push_back(u);
}
topo();
for(int i = 0; i < ans.size(); i++) w[ans[i]].print();
return 0;
}
Story
给定质数 $p$，有 $T$ 次询问，每次给出非负整数 $a,d,n$，求：
\[(\prod\limits_{i=0}^{n-1}(a+id))\bmod p\]$T,p\le 10^7$
题解
原式等价于 $d^n \prod\limits_{i=0}^{n-1}(\frac{a}{d}+i)$，然后考虑这样一个事实：
\[\prod\limits_{i=0}^{n-1}(M+i)=\frac{(M+n-1)!}{(M-1)!}\]于是直接预处理阶乘即可。时间复杂度 $O(T\log p +p)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e7 + 10;
ll fac[MAX_N], T, p;
inline ll read() {...}
inline void write(ll x) {...}
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {x = 1, y = 0; return;}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
ll inv(ll v) {
ll x, y;
exgcd(v, p, x, y);
return (x % p + p) % p;
}
ll qpow(ll a, ll b) {
ll ret = 1;
a = (a % p + p) % p;
while(b) {
if(b & 1) ret = (ret * a) % p;
a = (a * a) % p;
b >>= 1;
}
return ret;
}
int main() {
T = read(), p = read();
fac[0] = 1;
for(int i = 1; i <= p; i++) fac[i] = (fac[i - 1] * i) % p;
while(T--) {
ll a = read(), d = read(), n = read();
if(!d) write(qpow(a, n));
else {
ll M = a * inv(d) % p;
if(M + n - 1 > p) write(0);
else write(fac[M + n - 1] * inv(fac[M - 1]) % p * qpow(d, n) % p);
}
putchar('\n');
}
return 0;
}
- 上一篇 OI笔记 | 数列分块笔记
- 下一篇 OI笔记 | 杂类模板
♥