日记 - 伊埃斯的博客站

我们拥有分数。

T1

题意：输入 $n$ 和 $p$ ，求 $\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{p}\varphi(i^j)$ 。

我们首先用线性筛筛出 $\varphi(i),i \in [1,n]$ ，然后我们通过打表发现一个规律：

\begin{aligned} \varphi(x^1) & = \varphi(x) \times x^0 \\ \varphi(x^2) & = \varphi(x) \times x^1 \\ \varphi(x^3) & = \varphi(x) \times x^2 \\ & \vdots \\ \varphi(x^y) & = \varphi(x) \times x^{y - 1} \end{aligned}

于是我们把后面的 $\sum\limits_{j = 1}^{p}\varphi(i^j)$ 展开：

\begin{aligned} \sum\limits_{j = 1}^{p}\varphi(i^j) & = \varphi(x) \times x^0 + \varphi(x) \times x^1 + \cdots + \varphi(x) \times x^p \\ & = \varphi(x) \times (x^0 + x^1 + \cdots + x^p) \\ & = \varphi(x) \times \frac{x^p - 1}{x - 1} \end{aligned}

然后我们就得到了一个 $O(n \log_2 p)$ 的算法，应对 $n \le 1 \times 10^6$ 还可以，但是那该死的出题人设的数据范围是 $n \le 1 \times 10^7$ ，卡常也卡不过去，所以我们需要一些奇技淫巧把他弄成 $O(n \log_n p)$ 的。

code:

1
#include<bits/extc++.h>
2
#pragma GCC optimize(2)
3
#pragma GCC optimize(3)
4
#pragma GCC optimize("Ofast")
5
#pragma GCC target("avx")
6
#define re register
7
#define int long long
8
#define Inv(x) binpow(x,mod - 2)
9
using namespace std;
10
const int mod = 1e9 + 7;
11
const int maxn = 1e7 + 5;
12
int n,p;
13
bool ipr[maxn];
14
int pr[maxn],cnt;
15
int phi[maxn],inv[maxn],pw[maxn],low[maxn];
16
inline int binpow(int x,int y)
17
{
18
    re int ret = 1;
19
    while (y)
20
    {
21
        if (y & 1)
22
            ret = ret * x % mod;
23
        x = x * x % mod;
24
        y >>= 1;
25
    }
26
    return ret;
27
}
28
inline void prime(int up)
29
{
30
    phi[1] = 1;
31
    for (re int i = 2; i <= up; i++)
32
    {
33
        if (!ipr[i])
34
        {
35
            pr[++cnt] = i;
36
            low[i] = i;
37
            phi[i] = i - 1;
38
            inv[i] = Inv(i);
39
            pw[i] = binpow(i,p);
40
        }
41
        for (re int j = 1; j <= cnt; j++)
42
        {
43
            if (i * pr[j] > up)
44
                break;
45
            ipr[i * pr[j]] = 1;
46
            low[i * pr[j]] = pr[j];
47
            phi[i * pr[j]] = phi[i] * phi[pr[j]];
48
            if (i % pr[j] == 0)
49
            {
50
                phi[i * pr[j]] = phi[i] * pr[j];
51
                break;
52
            }
53
        }
54
    }
55
}
56
signed main()
57
{
58
    ios::sync_with_stdio(0);
59
    cin.tie(0);
60
    cout.tie(0);
61
    cin >> n >> p;
62
    prime(n);
63
    inv[1] = pw[1] = 1;
64
    for (int i = 2; i <= n; i++)
65
    {
66
        pw[i] = pw[low[i]] * pw[i / low[i]] % mod;
67
        inv[i] = inv[low[i]] * inv[i / low[i]] % mod;
68
    }
69
    re int ans = p;
70
    for (re int i = 2; i <= n; i++)
71
        ans = (ans + phi[i] * (pw[i] - 1 + mod) % mod * inv[i - 1] % mod) % mod;
72
    cout << ans;
73
    return 0;
74
}

一定把线性筛求欧拉函数给记住咯！

T2

题意：给定一颗有 $n$ 个节点的二叉树，每个节点上有一个 $\in [1,n]$ 的编号，满足任意除叶子节点的编号一定比两个子节点的编号大。钦定有 $m$ 个节点一定是叶子节点，输入 $n,m$ 和那 $m$ 个叶子节点的编号，求总共可以有多少种二叉树形态。

我们从大到小，模拟把每个数填进去的过程。设 $tmp$ 表示这个节点有多少个填法。那么最开始就肯定是 $1$ ，因为只有根节点这一个位置可以填。如果这个位置为钦定为叶子节点，那么 $tmp \leftarrow tmp - 1$ ，因为它会占一个位置，否则 $tmp \leftarrow tmp + 1$ ，因为即使它占了一个位置，它也会创造两个新的位置。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn = 1e6 + 5;
5
const int mod = 1e9 + 7;
6
int n,m;
7
bool b[maxn];
8
signed main()
9
{
10
    ios::sync_with_stdio(0);
11
    cin.tie(0);
12
    cout.tie(0);
13
    cin >> n >> m;
14
    for (int i = 1,x; i <= m; i++)
15
    {
16
        cin >> x;
17
        b[x] = 1;
18
    }
19
    int ans = 1,tmp = 1;
20
    for (int i = n; i >= 1; i--)
21
    {
22
        ans = ans * tmp % mod;
23
        tmp += b[i] ? -1 : 1;
24
    }
25
    cout << ans;
26
    return 0;
27
}

T3

没改，神秘小 dp。

T4

我们设这 $n$ 个数的异或和是 $sum$ 。那么当 $sum = 0$ 时很明显是平局。否则，他们一定靠 $sum$ 的最高位决出胜负。设 $sum$ 的最高位是 $pos$ ，那么把 $a_i \operatorname{and} 2^{pos}$ 提出来，我们就得到了一个 $01$ 串。且 $1$ 的数量为奇数。

我们注意到，当 $n$ 是偶数的时候，要么在 $i$ 为偶数的地方有奇数个 $1$ ，要么在 $i$ 为奇数的地方有。由于先手可以决定后手取的地方下标的奇偶性，所以当 $n$ 为偶数的时候，先手必胜。

那么当 $n$ 为奇数呢？为了不让后手变成上面的先手，所以先手一定要在第一次取一个 $1$ ，使 $1$ 的个数变成偶数，不然，后手变先手然后就必胜了。取完第一个 $1$ 过后，我们发现先手一定要和变成先手的后手取的一样。那么，我们把两边一样的都取完，那么剩下的肯定得是这个样子： $0011001111...$ ，也就是对于一个 $i \bmod 2 = 0$ ，有 $a_i = a_{i + 1}$ 。不然就不能和变成先手的后手取一样的了。

然后还有一个：就是 $1$ 的个数必须是 $4$ 的倍数，因为先手和后手会把每个 $1$ 都取完。如果不是 $4$ 的倍数，那么先手的手上就会有奇数个 $1$ ，加上最前面的 $1$ 就败了。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn = 1e5 + 5;
5
int n,sum;
6
int a[maxn];
7
bool calc(int s,int t)
8
{
9
    while (a[s] == a[t] && s < t)
10
        s++,t--;
11
    if (s > t)
12
        return 1;
13
    for (int i = s; i <= t; i += 2)
14
        if (a[i] != a[i + 1])
15
            return 0;
16
    return 1;
17
}
18
void solve()
19
{
20
    scanf("%lld",&n);
21
    sum = 0;
22
    for (int i = 1; i <= n; i++)
23
    {
24
        scanf("%lld",a + i);
25
        sum ^= a[i];
26
    }
27
    if (sum == 0)
28
        return (void)puts("Draw");
29
    int pos = 30;
30
    while (pos >= 0)
31
    {
32
        if (sum & (1 << pos))
33
            break;
34
        pos--;
35
    }
36
    for (int i = 1; i <= n; i++)
37
        a[i] = (a[i] >> pos) & 1;
38
    sum = 0;
39
    for (int i = 1; i <= n; i++)
40
        sum += a[i];
41
    if ((n & 1) == 0)
42
        return (void)puts("Alice");
43
    if (!a[1] && !a[n])
44
        puts("Bob");
45
    else if (sum % 4 == 1)
46
    {
47
        if (a[1] && a[n])
48
        {
49
            if (calc(1,n - 1) || calc(2,n))
50
                puts("Alice");
51
            else
52
                puts("Bob");
53
        }
54
        else if (a[1])
55
        {
56
            if (calc(2,n))
57
                puts("Alice");
58
            else
59
                puts("Bob");
60
        }
61
        else
62
        {
63
            if (calc(1,n - 1))
64
                puts("Alice");
65
            else
66
                puts("Bob");
67
        }
68
    }
69
    else
70
        puts("Bob");
71
}
72
signed main()
73
{
74
    int t;
75
    scanf("%lld",&t);
76
    while (t--)
77
        solve();
78
    return 0;
79
}

然而苦于码力不足，自己打出来的死活调不出来，只好借鉴的汪汪的代码。

Thanks for reading!

日记

周二 2月 25 2025

1441 字 · 10 分钟

life 日记