2024牛客暑期多校训练营1_给定两个整数 ,n,m,问有多少个长为 n 的非负整数数列 a,满足以下条件:1+2+ +=a

A. A Bit Common

Problem

给定两个整数 $n$ 和 $m$，问有多少个长度为 $n$ 的序列 { A } i = 1 n ( A i < 2 m ) \{A\}_{i=1}^n (A_i< 2^m) {A}i=1n​(Ai​<2m) 满足存在一个非空子序列的按位与之和为 $1$。答案对整数 $q$ 取模。

数据范围：$1\le n,m\le 5000,1\le q\le 10^9$

Soultion

先考虑一个问题：有多少个不同的序列 { B } i = 1 n ( B i < 2 m ) \{B\}_{i=1}^n (B_i< 2^m) {B}i=1n​(Bi​<2m) 使得按位与之和为 $0$，即 $B_1\&B_2\&\dots \&B_n=0$。

将 $B_i$ 转化为二进制的形式后，每一位上都至少存在一个 $0$，这样按位与后该位才能变为 $0$。对于长度为 $n$ 的序列每一位的方案数为 $2^n-1$（减去全为 $1$ 的情况），共有 $m$ 位，那么这样的序列个数共有 $(2^n-1{)}^m$ 个。用 $f_{i,j}$ 表示长度为 $i$，位数为 $j$ 时不同的序列个数，那么$f_{i,j}=(2^i-1{)}^j$。

回到原来的问题，序列 { A } i = 1 n \{A\}_{i=1}^n {A}i=1n​ 中的数可以分为奇数和偶数，其中如果存在一个非空子序列按位与之和为 $1$，那么这个子序列中的数只能是奇数。同时子序列得到的结果是 $000\dots 001$，那么其他奇数一起按位与得到结果也为 $1$，因此问题的条件可以转化为对于奇数需要满足按位与之和为 $1$。只需要把最后一位去掉，就可以转换为前面的形式，个数就是 $f_{i,m-1}$。

最后的答案为 ${\sum }_{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)f_{i,m-1}(2^{m-1}{)}^{n-i}$，其中 $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ 表示长度为 $n$ 的序列中奇数个数为 $i$ 的方案数，$f_{i,m-1}$ 表示的就是奇数的方案数，$(2^{m-1}{)}^{n-i}$ 表示偶数的方案数，$m-1$ 是因为偶数最后一位有限制，$n-i$ 是偶数的数量。

时间复杂度：$O(n^2)$，需要预处理组合数。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e3;
int n, m;
ll C[N + 5][N + 5], M;
ll fpow(ll a, ll b)
{
    ll res = 1;
    a %= M;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % M;
        }
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
int main()
{
    cin >> n >> m >> M;
    for (int i = 0; i <= N; i++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + C[n][i] * (fpow(fpow(2, i) - 1, m - 1)) % M * fpow(fpow(2, m - 1), n - i) % M) % M;
    }
    printf("%lld\n", ans);
    return 0;
}
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

B. A Bit More Common

Problem

给定两个整数 $n$ 和 $m$，问有多少个长度为 $n$ 的序列 { A } i = 1 n ( A i < 2 m ) \{A\}_{i=1}^n (A_i< 2^m) {A}i=1n​(Ai​<2m) 满足至少存在两个不同非空子序列的按位与之和为 $1$。答案对整数 $q$ 取模。

数据范围：$1\le n,m\le 5000,1\le q\le 10^9$

Soultion

先考虑一个问题：有多少个不同的序列 { B } i = 1 n ( B i < 2 m ) \{B\}_{i=1}^n (B_i< 2^m) {B}i=1n​(Bi​<2m) 使得按位与之和为 $0$，即 $B_1\&B_2\&\dots \&B_n=0$，同时缺少任何一个数都不等于零。

将 $B_i$ 转化为二进制的形式后，每一位上都至少存在一个 $0$，这样按位与后的该位才能变为 $0$。又要求缺少任何一个数都不等于零，那么对于每个数来说必须要存在至少一个特殊位，即除了这个数该位为 $0$，其它数在这一位都为 $1$。

先不考虑其他位的情况，只考虑这 $j$ 个特殊位的方案数。这里提供两种求解方法，任选一种都可以。

方法一：对于有 $j$ 个特殊位的序列，可以将这些特殊位看成不同的球，问题可以转换为将 $j$ 个不同的球放入 $n$ 个不同的箱子中且箱子非空的方案数，就是 $S(j,n)A_n^n$，其中 $S(j,n)$ 为第二类斯特林数，$A_n^n$ 为排列数。

方法二：用 $dp$ 的方法求解，记 $f_{i,j}$ 表示长度为 $i$ 共有 $j$ 个特殊位的方案数，状态转移方程如下：
$$f_{i,j}=i(f_{i,j-1}+f_{i-1,j-1})$$
解释：对于新的特殊位可以出现在原来的数中，此时有 $i\times f_{i,j-1}$ 种，也可以作为单独的一个数出现，这个数有 $i$ 个位置可以插入，此时有 $i\times f_{i-1,j-1}$ 种，将这两部分加起来即可。

记 $su{m}_i$ 表示长度为 $i$ 的序列的个数，那么 $su{m}_i={\sum }_{j=1}^m\left(\genfrac{}{}{0ex}{}{m}{j}\right)S(j,i)A_i^i(2^i-i-1{)}^{m-j}$，其中 $S(j,i)A_i^i$ 换成 $f_{i,j}$ 也可以。

解释：$\left(\genfrac{}{}{0ex}{}{m}{j}\right)$ 表示从 $m$ 位中选择 $j$ 个特殊位的方案数，$(2^i-i-1{)}^{m-j}$ 表示其他位的方案数，$(2^i-i-1)$ 是因为要减去全为一以及为特殊位的情况，共有 $i+1$ 种，剩下 $m-j$ 位。

回到原来的问题，其实该问题已经被解决了，题目要求的是至少存在两个不同的子序列，那么只要将上一个问题的答案减去只存在一个子序列的个数即可。而只存在一个子序列的个数可以通过之前考虑的问题得到。

最后的答案 ${\sum }_{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)((2^i-1{)}^{m-1}-su{m}_i)(2^{m-1}{)}^{n-i}$。

时间复杂度：$O(mn)$

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e3;
int n, m;
ll C[N + 5][N + 5], f[N + 5][N + 5], S[N + 5][N + 5], A[N + 5], p[N + 5], sum[N + 5], M;
ll fpow(ll a, ll b)
{
    ll res = 1;
    a %= M;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % M;
        }
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
int main()
{
    cin >> n >> m >> M;
    for (int i = 1; i <= N; 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]) % M;
        }
    }
    S[0][0] = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j) % M;
        }
    }
    A[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        A[i] = A[i - 1] * i % M;
    }
    // f[0][0] = 1;
    // for (int i = 1; i <= N; i++)
    // {
    //     for (int j = i; j <= N; j++)
    //     {
    //         f[i][j] = (f[i][j - 1] * i % M + f[i - 1][j - 1] * i % M) % M;
    //     }
    // }
    p[0] = 1;
    for (int i = 1; i <= N; i++)
    {
        p[i] = p[i - 1] * 2 % M;
    }

    for (int i = 1; i <= n; i++)
    {
        ll a = (p[i] - (i + 1) % M + M) % M, pre = 1;
        for (int j = m - 1; j >= i; j--)
        {
            sum[i] = (sum[i] + C[m - 1][j] * S[j][i] % M * A[i] % M * pre % M) % M;
            pre = pre * a % M;
        }
    }
    if (m == 1)
    {
        sum[1] = 1;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + C[n][i] * (fpow(p[i] - 1 + M, m - 1) - sum[i] + M) % M * fpow(p[n - i], m - 1) % M) % M;
    }

    printf("%lld\n", ans);
    return 0;
}
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

C. Sum of Suffix Sums

Problem

初始时数组为空，要求执行 $q$ 次操作，每次操作给定两个整数 $t$ 和 $v$，将数组中后 $t$ 个元素删除并将 $v$ 加入末尾。问每次操作后 ${\sum }_{i=1}^n{s}_i$ 的大小，$s_i=a_i+a_{i+1}+\cdots +a_n$。

数据范围：$1\le q\le 5\times 10^5,0\le v\le 10^9$。

Soultion

直接用栈模拟即可，每加入一个元素 $v$，答案增加 $v\times size$，$size$ 表示加入后数组的大小，每删除一个元素 $v$，答案减少 $v\times size$，$size$为删除前数组的大小。

时间复杂度：$O(q)$。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e3;
const ll M = 1000000007;
int q;
stack<ll> Q;
int main()
{
    cin >> q;
    ll ans = 0;
    for (int i = 1; i <= q; i++)
    {
        int t;
        ll v;
        cin >> t >> v;
        for (int i = 1; i <= t; i++)
        {
            ans = (ans - (ll)Q.size() * Q.top() % M + M) % M;
            Q.pop();
        }
        Q.push(v);
        ans = (ans + (ll)Q.size() * v) % M;
        printf("%lld\n", ans);
    }
    return 0;
}
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

H. World Finals

Problem

给定 $n$ 支队伍在第 46 届比赛的队名 $S$，解决问题数量 $p$，罚时 $t$；以及 $m$ 支队伍在第 47 届比赛的队名 $S$ ，解决问题数量 $p$，罚时 $t$。如果两届比赛中出现相同的队名，那么该队可以选择参加第46届比赛也可以选择参加第47届，问队伍名为 $lzr010506$ 的最好的名次是多少。

数据范围：$1\le n,m\le 10^5,1\le |S|\le 10,1\le p,t\le 10^9$。

Soultion

分别对每届比赛进行排序，对于排名在 $lzr010506$ 之前的队伍，并且在两届比赛中都出现，那么可以让这支队伍去另一届比赛，这样就能使得 $lzr010506$ 的排名更靠前，最后对两届比赛的结果取个 $min$ 即可。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6;
int n, m;
struct node
{
    string s;
    int p, t;
    node(string a, int b, int c)
    {
        s = a;
        p = b;
        t = c;
    }
};
bool cmp(node x, node y)
{
    return x.p == y.p ? x.t < y.t : x.p > y.p;
}
bool check(string s)
{
    string t = "lzr010506";
    if (s.size() != t.size())
    {
        return false;
    }
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] != t[i])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> n;
    vector<node> p1, p2;
    map<string, int> mp;
    for (int i = 0; i < n; i++)
    {
        string s;
        int p, t;
        cin >> s >> p >> t;
        p1.push_back(node(s, p, t));
        mp[s]++;
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        string s;
        int p, t;
        cin >> s >> p >> t;
        p2.push_back(node(s, p, t));
        mp[s]++;
    }
    sort(p1.begin(), p1.end(), cmp);
    sort(p2.begin(), p2.end(), cmp);
    int ans1 = 1, ans2 = 1;
    for (int i = 0; i < n; i++)
    {
        if (check(p1[i].s))
        {
            break;
        }

        if (mp[p1[i].s] == 1)
        {
            ans1++;
        }
    }
    for (int i = 0; i < m; i++)
    {
        if (check(p2[i].s))
        {
            break;
        }

        if (mp[p2[i].s] == 1)
        {
            ans2++;
        }
    }
    printf("%d\n", min(ans1, ans2));
    return 0;
}
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

I. Mirror Maze

Problem

给定四种镜子“-”、“|”、“/”、“\”，的反射方式，以及$n\times m$大小的镜子迷宫，现在有$q$束光线，问每束光线能够反射的不同镜子数量。

数据范围：$1\le n,m\le 1000,1\le q\le 10^5$。

Soultion

利用光的可逆性就能很好的解决该问题，首先从外面射向镜子迷宫的光线一定可以从某个位置射出，那么可以先将这些光线进行预处理，处理过后，内部没有经过的点形成一定是一个环。因为如果内部的光线可以从某个位置射出迷宫，那么在之前预处理的时候就应该经过了，这说明内部的光线形成的是环。因此分两种情况预处理即可，具体实现细节看代码。

时间复杂度：$O(nm+q)$。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e3;
int n, m, q, f[1100][1100][4], loop;
string s[1100];
map<pair<char, int>, int> mp;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct node
{
    int x, y;
    int d;
    node(int a, int b, int c)
    {
        x = a, y = b, d = c;
    }
};
vector<node> Q;
set<pair<int, int>> st;
void dfs(int x, int y, int d)
{
    if (f[x][y][d] != -1)
    {
        return;
    }
    f[x][y][d] = st.size();
    Q.push_back(node(x, y, d));

    int D = mp[{s[x][y], d}];
    int ex = x + dx[D], ey = y + dy[D];
    if (ex >= 1 && ex <= n && ey >= 1 && ey <= m)
    {
        if (d != D)
        {
            st.insert({x, y});
        }
        dfs(ex, ey, D);
    }
}
int main()
{
    mp[{'|', 0}] = 0, mp[{'|', 1}] = 1, mp[{'|', 2}] = 3, mp[{'|', 3}] = 2;
    mp[{'-', 0}] = 1, mp[{'-', 1}] = 0, mp[{'-', 2}] = 2, mp[{'-', 3}] = 3;
    mp[{'/', 0}] = 3, mp[{'/', 1}] = 2, mp[{'/', 2}] = 1, mp[{'/', 3}] = 0;
    mp[{'\\', 0}] = 2, mp[{'\\', 1}] = 3, mp[{'\\', 2}] = 0, mp[{'\\', 3}] = 1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] = '#' + s[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                f[i][j][k] = -1;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        st.clear();
        Q.clear();
        dfs(i, 1, 3);
    }
    for (int i = 1; i <= n; i++)
    {
        st.clear();
        Q.clear();
        dfs(i, m, 2);
    }
    for (int i = 1; i <= m; i++)
    {
        st.clear();
        Q.clear();
        dfs(1, i, 1);
    }
    for (int i = 1; i <= m; i++)
    {
        st.clear();
        Q.clear();
        dfs(n, i, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (f[i][j][k] == -1)
                {
                    st.clear();
                    Q.clear();
                    dfs(i, j, k);
                    for (auto it : Q)
                    {
                        int x = it.x, y = it.y, d = it.d;
                        f[x][y][d] = st.size();
                    }
                }
            }
        }
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int u, v, d;
        string t;
        cin >> u >> v >> t;
        if (t[0] == 'a')
        {
            d = 1;
        }
        else if (t[0] == 'b')
        {
            d = 0;
        }
        else if (t[0] == 'l')
        {
            d = 3;
        }
        else
        {
            d = 2;
        }
        printf("%d\n", f[u][v][d]);
    }
    return 0;
}
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