Index

Review

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

Solution

pk

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

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

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

type=1

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

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

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

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

看看 [i,i+s][i,i+s] 怎么求，可以 小学奥数 裂项处理 [i,i+s]=[i−1,i+s]−[i,i+s+1](i−1)−(i+s+1)=[i−1,i+s]−[i,i+s+1](−s−2)[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)=1−s−2([n,n+s+1]−[0,1+s])=1−s−2[n,n+s+1]F(n)=\dfrac1{-s-2}([n,n+s+1]-[0,1+s])=\dfrac1{-s-2}[n,n+s+1]

可以 O(s)O(s) 地求出

type=2

ansans 就是之前的数列隔一项取一项

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

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

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

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

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

问题转变为怎么求 GG

考虑将两项凑为一组

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

化简

 [i,i+s]−[i+1,i+s+1]=(i⋅[i+1,i+s])([i+1,i+s]⋅(i+s+1))=[i+1,i+s]⋅(i−i−s−1)=[i+1,i+s]⋅(−s−1)\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}

所以有

G(n,s)=∑i=1n[i+1,i+s]⋅(−s−1)i≡1(mod2)=∑i=1n[i,i+s−1]⋅(−s−1)i≡0(mod2)=B(n,s−1)⋅(−s−1)\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}

可以递归地处理 GG

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
//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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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