20210218 模拟赛总结

Index

Review

考的不错，主要是第一题做出来了，分数可观， 140pts。
但是后面两题的暴力分也没有打满，这是做的不够的一点。

Solution

pk

定义 $f(n,k)=(n-k+1)!\sum_{i=0}^{k-1}\dbinom{n-k}{i}\dbinom{k}{j-i-1}$ ，求 $\sum\limits_{i=L}^{R}f(i+s,i)$

经过打表可以发现 $f(n,n)=n$ 和 $f(n,k)=f(n,k+1)\cdot k$

化简得 $f(n,k)=\dfrac{n!}{(k-1)!}$

type=1

首先考虑 type=1 的情况，代入式子即得 $ans=\sum\limits_{i=L}^{R}\dfrac{(i+s)!}{(i-1)!}$

不严谨但是方便一点地表示 $i\cdot (i+1)\cdot (i+2)\cdots (j)$ 为 $[i,j]$

则 $ans=\sum\limits_{i=L}^{R}[i,i +s]$

设 $F(n)=\sum\limits_{i=1}^{n}[i,i+s]$ ，所以 $ans=F(R)-F(L-1)$

看看 $[i,i+s]$ 怎么求，可以 小学奥数 裂项处理 $[i,i+s]=\dfrac{[i-1,i+s]-[i,i+s+1]}{(i-1)-(i+s+1)}=\dfrac{[i-1,i+s]-[i,i+s+1]}{(-s-2)}$

然后式子就变成了 $F(n)=\dfrac1{-s-2}([n,n+s+1]-[0,1+s])=\dfrac1{-s-2}[n,n+s+1]$

可以 $O(s)$ 地求出

type=2

$ans$ 就是之前的数列隔一项取一项

不妨设 n 是偶数，不够的话补一项就是了

设 $A(n,s)=\sum\limits_{i=1}^{n}[i,i+s]\qquad i\equiv1\pmod2$

设 $B(n,s)=\sum\limits_{i=1}^{n}[i,i+s]\qquad i\equiv0\pmod2$

发现 $A(n)$ 和 $B(n)$ 很难求，所以设一个正负符号交错的数列 $G$ ，这样有 $A(n)=\dfrac{F(n)+G(n)}{2}$ 和 $B(n)=\dfrac{F(n)-G(n)}{2}$

即 $G(n,s)=\sum\limits_{i=1}^{n}(-1)^{i-1}[i,i+s]$

问题转变为怎么求 $G$

考虑将两项凑为一组

$G(n,s)=\sum\limits_{i=1}^{n}\left([i,i+s]-[i+1,i+s+1]\right)\qquad i\equiv1\pmod2$

化简

$$\begin{aligned} \ [i,i+s]-[i+1,i+s+1]&=(i\cdot[i+1,i+s])([i+1,i+s]\cdot(i+s+1))\\ &=[i+1,i+s]\cdot(i-i-s-1)\\ &=[i+1,i+s]\cdot (-s-1) \end{aligned}$$

所以有

$$\begin{aligned} G(n,s)&=\sum\limits_{i=1}^{n}[i+1,i+s]\cdot(-s-1)\qquad i\equiv1\pmod2\\ &=\sum\limits_{i=1}^{n}[i,i+s-1]\cdot(-s-1)\qquad i\equiv0\pmod2\\ &=B(n,s-1)\cdot(-s-1) \end{aligned}$$

可以递归地处理 $G$

下面解决如何递归处理 $F$ 的问题

设 $F(n,s)=xF(n,s-1)$ ，则有 $x=\dfrac{F(n,s)}{F(n,s-1)}$ 。

代入 type=1 时 $F$ 的公式即可解得 $x=\dfrac{(s+1)(n+s+1)}{s+2}$

而 $A(n,s)$ 和 $B(n,s)$ 可以由 $F(n,s)$ 和 $G(n,s)$ 求出。

所以可以一层一层地递归计算 $A,B,G,F$ 的值，直到 $s=0$ 时。这时 $A,B,G,F$ 都是等差数列，可以 $O(1)$ 计算出结果。

答案就是 $A(r)-A(l-1)$ 或者 $B(r)-B(l-1)$，注意细节。

加上预处理逆元可以做到总复杂度 $O(s)$。

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

namespace baoli {
    const int MAXN = 110;
    const int mod = 998244353;

    int mul[MAXN], C[MAXN][MAXN];

    void init() {
        mul[1] = mul[0] = 1;
        for (int i = 1; i <= 100; i++)
            (mul[i] = mul[i - 1] * i) %= mod;
        C[0][0] = 1;
        for (int i = 1; i <= 100; i++) {
            C[i][0] = C[i][i] = 1;
            for (int j = 1; j < i; j++) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
                //printf("C[%lld][%lld] = %lld\n", i, j, C[i][j]);
            }
        }
    }

    int f(int n, int k) {
        int res = mul[n - k + 1];
        int sum = 0;
        for (int i = 0; i < k; i++) {
            (sum += C[n - k][i] * C[k][i + 1]) %= mod;
        }
        return res * sum;
    }
    int main() {
        for (int i = 1; i <= 100; i++) {
            for (int k = 1; k <= i; k++) {
                printf("f[%d][%d] = %d\n", i, k, f(i, k));
            }
        }
    }
}

int L, R, s, type;

namespace subtask1 {
    const int mod = 998244353;
    int power(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) {
                (res *= a) %= mod;
            }
            (a *= a) %= mod;
            b >>= 1;
        }
        return res;
    }
    int inv(int x) {
        return power(x, mod - 2);
    }
    int calc(int n, int k) {
        int res = 1;
        for (int i = n; i <= n + k; i++) {
            (res *= i) %= mod;
        }
        (res *= inv(k + 1)) %= mod;
        return res;
    }
    void format(int &res) {
        if (res < 0) res += (-res / mod + 1) * mod;
        res %= mod;
    }
    signed main() {
        int res = calc(R, s + 1) - calc(L - 1, s + 1);
        format(res);
        cout << res << endl;
        return 0;
    }
}

namespace subtask2 {
    const int mod = 998244353;
    const int MAXN = 1e7 + 10;
    struct Value {
        int x, y, a, b;
        Value() {
            x = 0, y = 0, a = 0, b = 0;
        }
    };
    int n = 0;
    int inv[MAXN];
    Value calc(int k) {
        Value res;
        if (k > 0) {
            Value prev = calc(k - 1);
            res.y = prev.y * (k + 1) % mod * (n + k + 1) % mod * inv[k + 2] % mod;
            res.x = (mod - k - 1) * prev.b % mod;
            res.a = (res.y + res.x) % mod * inv[2] % mod;
            res.b = (res.y - res.x + mod) % mod * inv[2] % mod;
        } else {
            res.y = ((1 + n) % mod) * n % mod * inv[2] % mod;
            res.a = n * n % mod * inv[4] % mod;
            res.b = ((n + 2) % mod) * n % mod * inv[4] % mod;
            res.x = (res.a - res.b + mod) % mod;
        }
        return res;
    }
    void format(int &res) {
        if (res < 0) res += (-res / mod + 1) * mod;
        res %= mod;
    }
    signed main() {
        inv[1] = 1;
        for (int i = 2; i <= s + 10; i++) {
            inv[i] = inv[mod % i] * (mod - mod / i) % mod;
        }
        int l = L, r = R;
        if ((l + r) % 2 == 0) {
            if ((l + s) % 2 == 0) l++;
            else r++;
        }
        n = r;
        Value res = calc(s);
        int ans = 0;
        if ((l + s) % 2 == 1) { ans += res.a; }
        else { ans += res.b; }
        n = l - 1;
        res = calc(s);
        if ((l + s) % 2 == 1) ans -= res.a;
        else ans -= res.b;
        format(ans);
        cout << ans << endl;
        return 0;
    }
}

signed main() {
    fastin >> L >> R >> s >> type;
    if (type == 1) return subtask1::main();
    return subtask2::main();
}

---

leaflike

给定整点，曼哈顿距离为偶数之间的点有连边，另有给定的 $m$ 条边，求该图最大团。

很妙的题。
考虑将点按 $(abs(x)+abs(y))\mod2$ 分成两类。对于 m = 0 的情况就是两类点个数取 $\max$

trick: 发现对于一张图的最大团等价于其补图的最大独立集。
而这个图的补图是一个二分图，二分图最大独立集等于其总点数减去最大匹配。

int v[MAXN][MAXN];
vector<int> e[MAXN];
int tim[MAXN], mch[MAXN];
int t;
bool dfs(int cur) {
    if (tim[cur] == t) return false;
    tim[cur] = t;
    for (auto nxt : e[cur]) {
        if (mch[nxt] == 0 || dfs(mch[nxt])) {
            mch[nxt] = cur;
            return true;
        }
    }
    return false;
}
int main() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((abs(p[i].x) + abs(p[i].y)) % 2 == (abs(p[j].x) + abs(p[j].y)) % 2) {
                v[i][j] = 1;
            }
        }
    }
    for (int i = 1, p, q; i <= m; i++) {
        fastin >> p >> q;
        v[p][q] = v[q][p] = 1;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (!v[i][j]) {
                if ((abs(p[i].x) + abs(p[i].y)) % 2 == 1) {
                    e[i].push_back(j);
                    tot++;
                }
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        t = i;
        if (dfs(i)) res++;
    }
    cout << n - res << endl;
    return 0;
}

---

HNOI2021-Index