Nowcoder 2020 暑期多校训练（1）

一共 10 个题目，能做的有几个？

听完叉姐（？）讲题目~~最速传说快于洛谷~~，好多题目都是论文的结论题…… 队内群友对此以及讲题纷纷发表各自的高见，可大佬的关注点总是和咱菜鸡不太一样…… 咱也不知道，咱也不敢问（

↑ 要被大一队友嫌弃力，乌乌 ↑

多亏这次是校队全队参加比赛，hls 已经开始撰写队内题解了，这是好的，不然我属实补不了题了（

A : B-Suffix Array

对于字符串 $t_1t_2...t_k$ ，有函数 $B(t_1t_2...t_k) = b_1b_2...b_k$ 定义如下：
若存在下标 j < i 使得 $t_j = t_i$ ，那 $b_i = min_{1 \leq j \lt i, t_j = t_i} i - j$ ；
否则， $b_i = 0$ ；
对于给定长为 n 字符串 s 的 n 个后缀，根据 B 函数的值进行字典序排序；字符串 s 仅由 a 和 b 构成；
数据范围：n ≤ 1e5，Σn ≤ 1e6；

B : Infinite Tree

令 $mindiv(n)$ 为 n 大于 1 的最小因数；现对于全体正整数，在 n - $\frac n{mindiv(n)}$ 之间连边构成树；令 $\delta (u,v)$ 为节点 u v 之间的边数，给定 $w_1...w_n$ ，求 $min_u\sum^m_{i=1} w_i\delta(u,i!)$ 。
数据范围：1 ≤ m ≤ 1e5，0 ≤ wi ≤ 1e4，Σm ≤ 1e6；

C : Domino

有两个 n × m 的矩阵，由 1 × 2 的砖块和 2 × 1 的砖块密铺；你可以将 2 × 2 范围内的两块相同的砖块调转方向（换成两块另一种砖块），问你需要操作多少次才能使得两个矩阵中的砖块排布一致；
数据范围：n, m ≤ 1e3，n × m ≤ 2e6；

D : Quadratic Form

太麻烦了……

E : Counting Spanning Trees

二分图包含 X（n个节点）和 Y（m个节点）两个部分；每一个 $x_i$ 连接到了 Y 的前 $a_i$ 个节点；给定 n, m, a 和 mod，求在模 mod 意义下生成树的数量；
数据范围：1 ≤ n,m ≤ 1e5，1 ≤ mod ≤ 1e9，1 ≤ a ≤ m，Σn ≤ 1e6；

F : Infinite String Comparision

s 为字符串，定义 $s^\infty$ 为字符串 s 的无穷循环；现给定字符串 a, b，要求比较 $a^\infty, b^\infty$ ；
数据范围：1 ≤ |a|, |b| ≤ 1e5，Σs ≤ 1e6；

签到题，稍微优雅的暴力（直接比较）就可以过~~但是我白给两发~~；但是其实也是有正经做法的，原题解中说到：

通过 Periodicity Lemma，仅比较前 a + b - gcd(a, b) 个字符即可判断字符串大小；

所以，这个代码暴力的极限不是 LCM，而是定理中的 Periodicity Lemma；

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

inline longs gcd(longs a, longs b)
{
    if (a < b) swap(a, b);
    if (!b) return a;
    else return gcd(b, a % b);
}

string a, b;

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    while (cin >> a >> b)
        if (a.length() == b.length())
        {
            if (a == b) cout << '=' << endl;
            else if (a < b) cout << '<' << endl;
            else cout << '>' << endl;
        }
        else
        {
            longs _a = a.length(), _b = b.length();
            longs ca = 0, cb = 0, cnt = 0;
            longs lim = _a + _b - gcd(_a, _b);
            while (cnt < lim)
            {
                if (a[ca] != b[cb]) break;
                ca = (ca + 1) % _a;
                cb = (cb + 1) % _b;
                ++ cnt;
            }
            if (cnt == lim) cout << '=' << endl;
            else if (a[ca] < b[cb]) cout << '<' << endl;
            else cout << '>' << endl;
        }

    return 0;
}

那么什么是 Periodicity Lemma 呢？

关于 Periodicity Lemma

周期引理：字符串 S 有循环节 p 和 q 并满足 p + q ≤ |S| + gcd(p, q)，那么 gcd(p, q) 也是一个循环节；

在这一题里的用法？

显然，a 和 b 是待比较字符串（现设为 A 和 B，长度为 ∞）的循环节；我们先假设 A = B = S，那么 a 和 b 都是 S 的循环节；因为 |S| = ∞，所以 a + b - gcd(a, b) ≤ |S| 可以使用周期引理：gcd(a, b) 是 S 的循环节；因为串 gcd(a, b) 较短，它成为了循环节，则整个串显然相同；

如果 A，B 的前 a + b - gcd(a, b) 位不相同，则不能被看作是一个字符串，上述假设就失效了；这时也可以判定字符串的字典序大小，直接输出即可；

简单的说，若两个字符串相等的假设成立，那么就一定可以证明 gcd(a, b) 长度的字串是循环节，这个串的长度小于 a 和 b，且再使用引理的过程中已经判等了，所以两个串相等，假说也成立；

引理证明？

组内大佬证明了，我学会了再发上来；

先贴另一个组内大佬的证法 ↑

G : BaXianGuoHai, GeXianShenTong

太长了不翻译了……

H : Minimum-cost Flow

有一个网络，包括 n 个节点和 m 个弧边，每条边有费用 c；
进行 q 次询问，每个询问当所有边的容量为 u/v 时，将单位流量从节点 1 到节点 n 所需要的最小费用；
可行时，输出最小费用，否则输出 NaN；
数据范围：2 ≤ n ≤ 50，1 ≤ m ≤ 100，c, q ≤ 1e5，u, v ≤ 1e9；Σm ≤ 1e4，Σq ≤ 1e6；

I : 1 or 2

一张图，有 n 个点，给定 m 条边；问可不可以选出一些边，使得第 i 个点恰好连接了 $d_i$ 条边；只需要判断是否可行，而无需输出具体选择方案。
数据规模：不超过 100 组测试数据；n ≤ 50，m ≤ 100， $d_i \in$ {1, 2}；

J : Easy Integration

求 $\int_0^1 (x - x^2)^n dx$ 在 998244353 下的模，n ≤ 1e6；不超过 1e5 组数据。

一个计算题，因为大一队友光速推出公式所以我就直接码代码了；没想到还是有点麻烦的……

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 1, ch = getchar();
    while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

const longs mod = 998244353;
const longs p = mod - 2;

int fracMod(longs a, longs b)   // 费马小定理法
{
    auto n = p;
    longs ans = 1;
    while (n)
    {
        if (n & 1) ans = (ans * b) % mod;
        b = (b * b) % mod;
        n >>= 1;
    }
    ans = (ans * a) % mod;
    return (int) ans;
}

const int N = 1e6 + 5;
longs ans[N];

auto init = []
{
    longs a = 1, b = 1;
    for (longs i = 1; i < N; ++ i)
    {
        a = (a * i) % mod;
        b = (2 * b * (2 * i + 1)) % mod;
        ans[i] = fracMod(a, b);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    init();
    longs n;
    while (cin >> n) cout << ans[n] << endl;

    return 0;
}

Nowcoder 2020 暑期多校训练 （1）