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;
}

低价购买

洛谷 P1108

求最长下降子序列的长度，以及达到该长度的最长下降子序列数。

题解

见注释。参考代码：

#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] 序列操作

洛谷 P2572

给定一个 $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

洛谷 P2986

给出一个既有点权又有边权的树，求出它的重心到所有点的距离之和。

题解

洛谷 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

洛谷 P8848

给出一个序列 $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] 排水系统

洛谷 P7113

对于一个城市来说，排水系统是极其重要的一个部分。

有一天，小 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;
}

Published on Nov 20, 2022 in categories Solution

页面访问次数

♥