这一场的小白月赛对萌新真的友好，连我这个蒟蒻都能切66题。~~（赛后发现有并查集的题又能切一题）。~~主要是本场要涉及的算法也不算很多，卡我的似乎都是数论的题:pensive:。

因为本场有几道分数结果要取1e9+71e9+7模，如果不太懂，可以戳这的A题。（快速幂+费马大定理求逆元）

J. 异或和之和 #组合公式 #逆元 #位运算

题目链接

题意

给定含有nn个正整数的数组，现要你从该数中任取33个元素进行异或运算后再总的求和的值。即，从数组中取一共Cn3C^3_n个三元组{a,b,c}\{ a,b,c \}，先计算这些三元组内部异或(a⊕b⊕ca\oplus b\oplus c)，再对所有异或结果进行求和，注意要对1e9+71e9+7取模。

分析

对于位运算后求其和，需要用到按位统计求贡献的思想。也就说，我们枚举每一数位，讨论在当前特定数位ii下，三三整数进行组合，找到某个三元组在第ii位下异或结果能够为11的（说明对总和结果贡献+1+1），统计有多少个贡献值为11的三元组，乘上该特定数位ii下对应的2i2^i（权重），实际上就是对总和的加成。

我们可以发现，三元内部某一相同的数位如果异或和为11，这一数位下的情况，要么是1⊕1⊕11\oplus1\oplus1，要么0⊕0⊕10\oplus0\oplus1。也就说，我们如果能找到某个三元组合在某个位下是1 1 11\ 1\ 1或者0 0 10\ 0\ 1组合（0 0 10\ 0\ 1组合与0 1 00\ 1\ 0组合是等价的，因为异或满足交换律），对总和的贡献值就为11了。

接下来，我们统计，数组中有多少整数在第ii数位下为11，记录为count[i]count[i]。那么能够组合1 1 11\ 1\ 1的组合数为Ccount[i]3C^3_{count[i]}，能够组合0 0 10\ 0\ 1的组合数为Cn−count[i]2×count[i]C^2_{n - count[i]} \times count[i]，总的组合数为Ccount[i]3+Cn−count[i]2×count[i]C^3_{count[i]}+C^2_{n - count[i]} \times count[i]，那么第ii位，对最终求和结果的贡献值即为2i×(Ccount[i]3+Cn−count[i]2×count[i])2^i\times (C^3_{count[i]}+C^2_{n - count[i]} \times count[i])。枚举所有ii，对贡献值求和即可。

之所以先把JJ题放前面，是为了引入组合公式写法（BB题要用到）。

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
#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;
using ll = long long;
using ld = long double;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int n, cnt[65];
ll ans;
ll quickPower(ll base, ll power) {
    ll ans = 1;
    while (power > 0) {
        if (power & 1) ans = ans * base % MOD;
        power >>= 1;
        base = (base * base) % MOD;
    }
    return ans;
}
ll Inv(ll x) { //逆元求分母在取模意义下的值
    return quickPower(x, MOD - 2);
}
ll C(ll x, ll y) { //组合公式（取模意义下）
    if (x < y) return 0;
    ll res = 1;
    for (ll i = 0; i < y; i++) {
        res = res * (x - i) % MOD; //分子
        res = res * Inv(i + 1) % MOD;  //分母
    }
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int j = 0; ll x;
        scanf("%lld", &x);
        while (x) {
            cnt[j++] += (x & 1);
            x >>= 1;
        }
    }
    for (int i = 0; i < 64; i++) {
        ll C_3 = C(cnt[i], 3), C_2 = C(n - cnt[i], 2);
        ans = ans + (1LL << i) % MOD * (C_3 + C_2 * (ll)cnt[i] % MOD) % MOD;
        ans = ans % MOD;
    }
    printf("%lld\n", ans % MOD);
    return 0;
}

B. k-size字符串 #组合公式 #逆元

题目链接

题意

k−sizek-size字符定义为，字符串恰好存在kk个连续段（相同连续字母组成的子串）。现给定nn个字母aa字符，mm个字母bb字符，组成长度为n+mn+m的k−sizek-size字符串，问有多少种组成方式（对1e9+71e9+7取模）

分析

先特判下条件，当n+m<kn+m<k时，即要求的连续段超过了字符串长度，无法组合，答案为00；当k=1k=1时，由于题目给定至少一个aa和至少一个bb，至少能组成组成22个连续段，无法满足k=1k=1，答案也为00；

为了方便地分隔出连续段，我们不妨先取**kk个字符，排成这样的排列（即a，ba，b字母相互交错）：ababab...ababab...。此时的串不但长度为kk，同时也满足存在kk个连续段。那么还有剩余的字母a,ba,b呢？（简而言之，就是采用挡板法**的思想，但是有些小细节要注意下）

  • 当kk为奇数的时候，此时的串，

    如果第一个字符排的是aa，最后一个字符一定也是aa，即ababab...abaababab...aba；此时我已将⌊k/2⌋+1\lfloor k/2\rfloor+1个aa、⌊k/2⌋\lfloor k/2\rfloor个bb排到上述串中了。现在需要将剩下的n−(⌊k/2⌋+1)n-(\lfloor k/2\rfloor+1)个aa（即有n−(⌊k/2⌋+1−1)n-(\lfloor k/2\rfloor+1-1)个挡板插入空位）插到原串中的每个aa附近（即有⌊k/2⌋+1\lfloor k/2\rfloor+1个挡板），允许对原串中某个aa不插入剩下的aa（即允许空盒）。联想到组合数学中的挡板法（见下面的补充，注意这里是非空盒子），对于字符aa的方案数为Cn−1⌊k/2⌋+1−1C_{n-1}^{\lfloor k/2 \rfloor + 1 - 1}。此外，还需要将剩下的n−(⌊k/2⌋)n-(\lfloor k/2\rfloor)个bb插到原串中每个bb（共⌊k/2⌋\lfloor k/2\rfloor个）附近，和上面同理，对于字符bb的方案数为Cm−1⌊k/2⌋−1C_{m-1}^{\lfloor k/2 \rfloor - 1}。因此由乘法原理，ababab...abaababab...aba方案数为Cn−1⌊k/2⌋+1−1×Cm−1⌊k/2⌋−1C_{n-1}^{\lfloor k/2 \rfloor + 1 - 1} \times C_{m-1}^{\lfloor k/2 \rfloor - 1} 。

    关于挡板法：有相同的nn个球，要将所有球插到mm个不同盒子且每个盒子一定要**“非空”**，相当于有m−1m-1个挡板，插入到n−1n-1个可插入空隙，组合数共有Cn−1m−1C_{n-1}^{m-1}。

    然而，如果每个盒子不一定非空呢？我们可以先从外部给每个盒子分别借来一个球（从而保证每个盒子此时已经有一个盒子，进而可以使用上面的挡板法了），即总共借来了mm个球，现总共有n+mn+m个球（n+m−1n+m-1个可插入空隙），还是m−1m-1个挡板，组合数为Cn+m−1m−1C^{m-1}_{n+m-1}。

    同理，如果如果第一个字符排的是bb，最后一个字符一定也是bb，即bababa...babbababa...bab；此时我已将⌊k/2⌋\lfloor k/2\rfloor个aa、⌊k/2⌋+1\lfloor k/2\rfloor+1个bb排到上述串中了。按照上面的方法，类比得到组合数为Cn−1⌊k/2⌋−1×Cm−1⌊k/2⌋+1−1C_{n-1}^{\lfloor k/2 \rfloor - 1} \times C_{m-1}^{\lfloor k/2 \rfloor + 1 - 1} 。

    综上，由加法原理，当kk为奇数的时候，组合数有Cn−1⌊k/2⌋+1−1×Cm−1⌊k/2⌋−1+Cn−1⌊k/2⌋−1×Cm−1⌊k/2⌋+1−1C_{n-1}^{\lfloor k/2 \rfloor + 1 - 1} \times C_{m-1}^{\lfloor k/2 \rfloor - 1}+C_{n-1}^{\lfloor k/2 \rfloor - 1} \times C_{m-1}^{\lfloor k/2 \rfloor + 1 - 1}。

  • 当kk为偶数时，如果第一个字符排的是aa，最后一个字符一定也是bb，即ababab...abababab...ab，方法还是采用上面的，方案数为Cn−1k/2−1×Cm−1k/2−1C_{n-1}^{k/2- 1} \times C_{m-1}^{k/2- 1}；如果第一个字符排的是bb，最后一个字符一定也是aa，即bababa...babababa...ba，方法还是采用上面的，方案数一样是为Cn−1k/2−1×Cm−1k/2−1C_{n-1}^{k/2- 1} \times C_{m-1}^{k/2- 1}；

    综上，当kk为奇数的时候，组合数有2×Cn−1k/2−1×Cm−1k/2−12\times C_{n-1}^{k/2- 1} \times C_{m-1}^{k/2- 1}。

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
#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
ll ans;
int n, m, k;
ll quickPower(ll base, ll power) {
    ll ans = 1;
    while (power > 0) {
        if (power & 1) ans = ans * base % MOD;
        power >>= 1;
        base = (base * base) % MOD;
    }
    return ans;
}
ll Inv(ll x) { //逆元求分母在取模意义下的值
    return quickPower(x, MOD - 2);
}
ll C(ll x, ll y) { //组合公式（取模意义下）
    if (x < y) return 0;
    ll res = 1;
    for (ll i = 0; i < y; i++) {
        res = res * (x - i) % MOD; //分子
        res = res * Inv(i + 1) % MOD;  //分母
    }
    return res;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    if (n + m < k || k == 1)
        ans = 0;
    else if (k & 1)
        ans = (C(n - 1, k / 2 + 1 - 1) * C(m - 1, k / 2 - 1    ) % MOD 
             + C(n - 1, k / 2 - 1    ) * C(m - 1, k / 2 + 1 - 1) % MOD) % MOD;
    else
        ans = 2 * C(n - 1, k / 2 - 1) * C(m - 1, k / 2 - 1) % MOD;
    printf("%lld\n", ans);
    return 0;   
}

C. 白魔法师

题目链接

题意

树上有n(n≤1e5)n(n\leq1e5)个点，每个点为黑色或白色。你可选定一个点，将其染为白色。你要保证染完后整颗树当中最大的白色连通块（该连通子图上所有点均为白色）尽可能大，现要你求出最大白色连通块大小。

分析

先利用题目给定的边，将白色点合并为连通块，合并完后统计每个连通块的规模大小。然后枚举每一个黑色点的邻接点所在连通块的总大小，更新最值即可。

所有点是白色点的情况，需要特判一下，答案为11。赛场上我忘记特判，直接白给

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
#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
int fa[MAXN], n, sz[MAXN], cnt = 0;
vector<int> H[MAXN];
bool isWhite[MAXN];
string str;
int findSet(int x) {
    if (x != fa[x]) {
        fa[x] = findSet(fa[x]);
    }
    return fa[x];
}
int main() {
    scanf("%d", &n);
    cin >> str;
    for (int i = 0; i < str.length(); i++) {
        isWhite[i + 1] = (str[i] == 'W');
        fa[i + 1] = i + 1;
    }
    for (int i = 1, u, v; i <= n - 1; i++) {
        scanf("%d%d", &u, &v);
        H[u].push_back(v);
        H[v].push_back(u);
        if (isWhite[u] && isWhite[v]) {
            int pu = findSet(u), pv = findSet(v);
            fa[pu] = pv;
        }
    }
    for (int i = 1; i <= n; i++) findSet(i);
    for (int i = 1; i <= n; i++) 
        if (isWhite[i]) {
            sz[fa[i]]++; cnt++;
        }
    int most = 0;
    if (cnt == n) most = n;
    else {
        for (int i = 1; i <= n; i++) {
            if (isWhite[i]) continue;
            int sum = 1;
            for (int j = 0; j < H[i].size(); j++) {
                int v = H[i][j]; if (!isWhite[v]) continue;
                sum += sz[fa[v]];
            }
            most = max(most, sum);
        }
    }
    printf("%d\n", most);
}

G. 解方程 #二分思想

题目链接

题意

解方程xa+bln⁡x=cx^a+b\ln x=c，其中1≤a≤3，1≤b,c≤1e91\leq a\leq 3，1\leq b,c\leq 1e9，解出的xx误差不超过1e−71e-7。

分析

考虑到a,ba,b数据范围下界，左边等式是个单调增加的函数。又因为cc下界大于00，当x=1x=1时，左边等式≤c\leq c。故二分时初始下界lo=1lo = 1。显然上界为1e91e9。

这里要注意下，由官方题解，doubledouble的精度不够高，后面二分时r−lr-l无限不动，导致TLETLE。应换用long doublelong\ double类型。

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
#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;
using ll = long long;
using ld = long double;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int a, b, c;
ld calculate(ld x) {
    ld rev = 1;
    for (int i = 1; i <= a; i++) rev *= x;
    rev += b * log(x);
    return rev;
}
int main() {
    scanf("%d%d%d", &a, &b, &c);
    ld lo = 1, hi = 1e9 + 5;
    while (hi - lo > EPS) {
        ld mid = (ld)(lo + hi) / 2;
        if (calculate(mid) - (ld)c >= 0) hi = mid;
        else lo = mid;
    }
    printf("%.7Lf\n", lo);
}