伊埃斯的小站
日记

日记

Tue Feb 25 2025
10 分钟
life 日记
1457 字

我们拥有分数。

T1#

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

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

φ(x1)=φ(x)×x0φ(x2)=φ(x)×x1φ(x3)=φ(x)×x2⋮φ(xy)=φ(x)×xy−1\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}

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

∑j=1pφ(ij)=φ(x)×x0+φ(x)×x1+⋯+φ(x)×xp=φ(x)×(x0+x1+⋯+xp)=φ(x)×xp−1x−1\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(nlog⁡2p)O(n \log_2 p) 的算法，应对 n≤1×106n \le 1 \times 10^6 还可以，但是那该死的出题人设的数据范围是 n≤1×107n \le 1 \times 10^7，卡常也卡不过去，所以我们需要一些奇技淫巧把他弄成 O(nlog⁡np)O(n \log_n p) 的。

code:

CPP
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
#include<bits/extc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define re register
#define int long long
#define Inv(x) binpow(x,mod - 2)
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e7 + 5;
int n,p;
bool ipr[maxn];
int pr[maxn],cnt;
int phi[maxn],inv[maxn],pw[maxn],low[maxn];
inline int binpow(int x,int y)
{
    re int ret = 1;
    while (y)
    {
        if (y & 1)
            ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
inline void prime(int up)
{
    phi[1] = 1;
    for (re int i = 2; i <= up; i++)
    {
        if (!ipr[i])
        {
            pr[++cnt] = i;
            low[i] = i;
            phi[i] = i - 1;
            inv[i] = Inv(i);
            pw[i] = binpow(i,p);
        }
        for (re int j = 1; j <= cnt; j++)
        {
            if (i * pr[j] > up)
                break;
            ipr[i * pr[j]] = 1;
            low[i * pr[j]] = pr[j];
            phi[i * pr[j]] = phi[i] * phi[pr[j]];
            if (i % pr[j] == 0)
            {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> p;
    prime(n);
    inv[1] = pw[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        pw[i] = pw[low[i]] * pw[i / low[i]] % mod;
        inv[i] = inv[low[i]] * inv[i / low[i]] % mod;
    }
    re int ans = p;
    for (re int i = 2; i <= n; i++)
        ans = (ans + phi[i] * (pw[i] - 1 + mod) % mod * inv[i - 1] % mod) % mod;
    cout << ans;
    return 0;
}

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

T2#

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

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

code:

CPP
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
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int n,m;
bool b[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1,x; i <= m; i++)
    {
        cin >> x;
        b[x] = 1;
    }
    int ans = 1,tmp = 1;
    for (int i = n; i >= 1; i--)
    {
        ans = ans * tmp % mod;
        tmp += b[i] ? -1 : 1;
    }
    cout << ans;
    return 0;
}

T3#

没改，神秘小 dp。

T4#

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

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

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

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

code:

CPP
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
#include<bits/extc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n,sum;
int a[maxn];
bool calc(int s,int t)
{
    while (a[s] == a[t] && s < t)
        s++,t--;
    if (s > t)
        return 1;
    for (int i = s; i <= t; i += 2)
        if (a[i] != a[i + 1])
            return 0;
    return 1;
}
void solve()
{
    scanf("%lld",&n);
    sum = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld",a + i);
        sum ^= a[i];
    }
    if (sum == 0)
        return (void)puts("Draw");
    int pos = 30;
    while (pos >= 0)
    {
        if (sum & (1 << pos))
            break;
        pos--;
    }
    for (int i = 1; i <= n; i++)
        a[i] = (a[i] >> pos) & 1;
    sum = 0;
    for (int i = 1; i <= n; i++)
        sum += a[i];
    if ((n & 1) == 0)
        return (void)puts("Alice");
    if (!a[1] && !a[n])
        puts("Bob");
    else if (sum % 4 == 1)
    {
        if (a[1] && a[n])
        {
            if (calc(1,n - 1) || calc(2,n))
                puts("Alice");
            else
                puts("Bob");
        }
        else if (a[1])
        {
            if (calc(2,n))
                puts("Alice");
            else
                puts("Bob");
        }
        else
        {
            if (calc(1,n - 1))
                puts("Alice");
            else
                puts("Bob");
        }
    }
    else
        puts("Bob");
}
signed main()
{
    int t;
    scanf("%lld",&t);
    while (t--)
        solve();
    return 0;
}

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