🫟2024牛客暑假多校训练营Day1||补题

A-Bit Common

题意

计算满足长度为 $n$ ，每个元素小于 $2^m$ ，且存在至少一个子序列满足按位 $AND$ 后是 $1$ 的序列的数量。

答案对正整数 $q$ 取模。

数据范围

$1\leq n,m\leq 5000$
$1\leq q\leq 10^9$

思路

按位分析，对于一个长度为 $n$ 的序列，序列中的数分为 $k$ 个末尾是 $1$ 的数和 $n-k$ 个末尾是 $0$ 的数。

末尾为 $1$ 的数中，除末位以外的数位（ $m-1$ 位），每一位的组合是 $2^k-1$ 种（要除去全为1的情况）。
末尾为 $0$ 的数中，除末位以外数位上的取值是任意的。
选择哪些数是末尾 $1$ 需要考虑组合数。

所以，总方案数是：

\binom{n}{k}\times (2^k-1)^{m-1}\times (2^{n-k})^{(m-1)} = \binom{n}{k}\times (2^n-2^{n-k})^{m-1}

最后对 $q$ 取模即可。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const ll maxn = 5050;
5

6
ll qpow(ll a, ll b, ll m) {
7
    // 快速幂
8
    ll res = 1;
9
    while (b) {
10
        if (b & 1)res = res * a % m;
11
        a = a * a % m;
12
        b >>= 1;
13
    }
14
    return res % m;
15
}
16

17
ll C[maxn][maxn];
18

19
void solve() {
20
    ll n, m, q;
21
    cin >> n >> m >> q;
22
    C[0][0] = 1;
23
    for (ll i = 1;i <= n;i++) {
24
        C[i][0] = 1, C[i][i] = 1;
25
        for (ll j = 1;j < i;j++) {
26
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % q;
27
        }
28
    }
29
    ll ans = 0;
30
    for (ll k = 1;k <= n;k++) {
31
        ll tmp = C[n][k];
32
        ll x = (qpow(2, n, q) - qpow(2, n - k, q) + q) % q;
33
        tmp *= qpow(x, m - 1, q);
34
        tmp %= q;
35
        ans = (ans + tmp + q) % q;
36
    }
37
    cout << ans % q << "\n";
38
}
39

40
int main() {
41
    int _ = 1;
42
    // cin >> _;cin.get();
43
    while (_--)
44
        solve();
45

46
    return 0;
47
}

B-A Bit More Common

题意

在A题的条件下，增加要求满足存在两个不同的非空子序列 $AND$ 和是 $1$ 。

数据范围

$1\leq n,m\leq 5000$
$1\leq q \leq 10^9$

思路

有A题的基础，我们已知至少有 $1$ 个子序列的组合数，接下来我们计算只有 $1$ 个子序列的组合数。两者相减即可求出答案。

满足只有1个子序列的组合数所代表的情况是这样的：

\begin{aligned} let:k=3\\ 101111\\ 010101\\ 111011 \end{aligned}

需要满足每一个竖列至少有一个特殊的 $0$ （这个0同时是该数位上唯一的0），且这k个数每个数至少有1个 $0$ （条件2）。

对于偶数的组合种数还是不变的，为 $\binom{n}{k}\times 2^{(n-k)(m-1)}$ 。

当 $k=1$ 时，子序列是 $\\{0b00000001\\}$ ，只有一个数，剩余的 $n-k$ 个数都是偶数。
当 $k\neq 1$ 时，考虑：一共有 $m-1$ 个特殊 $0$ ，每个 $0$ 有对应的数位，要将这 $m-1$ 个 $0$ 分配到 $k$ 个位置（位置并不互相区分），每个位置至少有 $1$ 个，也就是第二类斯特林数。

考虑状态转移：

现在有 $i$ 个数，要从 $j-1$ 个特殊位的基础上再增加一个特殊0，这个特殊位要么增加到第 $i$ 个数（第 $i$ 个数已经有至少 $1$ 个特殊 $0$ ）上，要么增加到前 $i-1$ 个（已经至少包含一个特殊 $0$ 的）数上，这两种增加方法都有 $i$ 种不同的方案。

这 $i$ 个数中要包含 $j$ 个特殊 $0$ 的方案数记为 $f[i][j]$ ，则存在递推式：

f[i][j]= i\times (f[i-1][j-1] + f[i][j-1])

考虑到只有 $k$ 个数中特殊 $0$ 的个数大于等于k时的方案数才是有效的，同时，每个有效方案中，每一列除了作为特殊 $0$ 的位置以外的位置都可以任意填（只要不是全1或者只有1个特殊 $0$ 的情况），故这 $k$ 个奇数的方案总数是 $\sum_{t=k}^{m-1} f[k][t]\times (2^k-1-k)^{m-1-t}$ ，再乘此时的偶数方案数，即为 $k$ 时的总数。

代码

1
ll qpow(ll a, ll b, ll m) {
2
    // 快速幂
3
    ll res = 1;
4
    a %= m;
5
    while (b) {
6
        if (b & 1)res = res * a % m;
7
        a = a * a % m;
8
        b >>= 1;
9
    }
10
    return res % m;
11
}
12

13
ll C[maxn][maxn];
14
ll f[maxn][maxn];
15

16
void solve() {
17
    ll n, m, q;
18
    cin >> n >> m >> q;
19
    C[0][0] = 1ll;
20
    for (ll i = 1;i <= 5000;i++) {
21
        C[i][0] = 1, C[i][i] = 1;
22
        for (ll j = 1;j <= 5000;j++) {
23
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % q;
24
        }
25
    }
26
    ll ans = 0;
27
    for (ll k = 1;k <= n;k++) {
28
        ll tmp = C[n][k];
29
        ll x = (qpow(2ll, n, q) - qpow(2ll, n - k, q) + q) % q;
30
        tmp *= qpow(x, m - 1ll, q);
31
        tmp %= q;
32
        ans = (ans + tmp + q) % q;
33
    }
34

35
    ll res = qpow(2ll, (n - 1) * (m - 1) % q, q) * n % q;
36
    // 存在1个子序列AND=1的，减去只有1个子序列AND=1的
37
    f[0][0] = 1ll;
38
    for (ll i = 1;i <= 5000;i++) {
39
        for (ll j = i;j <= 5000;j++) {
40
            f[i][j] = i * ((f[i - 1][j - 1] + f[i][j - 1]) % q) % q;
41
        }
42
    }
43
    for (ll k = 2;k <= n;k++) {
44
        ll tmp = qpow(2ll, (n - k) * (m - 1) % q, q) % q * C[n][k] % q;
45
        ll tmp2 = (qpow(2ll, k, q) - 1ll - k + q) % q;
46
        ll cur = 1ll;
47
        for (ll t = m - 1;t >= k;t--) {
48
            res = (res + f[k][t] * cur % q * C[m - 1][t] % q * tmp % q) % q;
49
            cur = tmp2 * cur % q;
50
        }
51
    }
52

53
    cout << (ans - res + q) % q << "\n";
54
}

C-Sum of Suffix Sums

题意

维护一个初始为空的非负整数序列，支持 $q$ 次如下操作：

每次移除末尾的 $t$ 个整数，然后在末尾假如一个整数 $v$ ，操作后输出当前序列所有后缀和的总和，答案对 $10^9+7$ 取模。

数据范围

$1\leq q\leq 5\times 10^5$
$0\leq v\leq 10^9$

思路

每个数对后缀和总和的贡献是它当前位置的序号乘以它本身的值，也就是 $a_i$ 的贡献是 $a_i\times i$ 。根据这个特点和数据范围，我们可以维护后缀和总和。

代码

1
void solve() {
2
    ll q;cin >> q;
3
    vector<ll>a;
4
    ll tot = 0;
5
    while (q--) {
6
        ll t, v;cin >> t >> v;
7
        v %= mo;
8
        for (ll i = 0;i < t;i++) {
9
            if (a.empty())break;
10
            ll x = a.back();
11
            tot -= x * a.size();
12
            tot = (tot + mo) % mo;
13
            a.pop_back();
14
        }
15
        a.push_back(v);
16
        ll n = a.size() % mo;
17
        tot = (tot + v * n % mo + mo) % mo;
18
        cout << tot << "\n";
19
    }
20
}

H-World Finals

签到题。

题意

lzr010506队伍可以参加46th的WF和47th的WF，这两个WF将同时举行，所以lzr010506必须选择其中一个参加。lzr010506可以预知每个队伍的在比赛中的成绩（过题数和罚时），排名规则为过题数多优先，过题数相同则罚时少优先。

除了lzr010506队伍，还有其他有资格参加两场比赛的队伍。提问，在给出所有队伍的预测成绩之后，lzr010506队伍能够获得的最好成绩排名是多少。

数据范围

$1 \leq number of teams \leq 105$

思路

最优情况是，除了lzr010506队伍，同时可以参加两场比赛的队伍都参加lzr010506队伍没有参加那一场，然后计算最佳排名即可。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
struct team {
6
    string s;
7
    ll p, t;
8
    bool operator<(const team& other)const {
9
        if (other.p == p)return other.t > t;
10
        return other.p < p;
11
    }
12
};
13

14
void solve() {
15
    ll n;cin >> n;
16
    vector<team>t46(n);
17
    map<string, bool>mp46;
18
    for (ll i = 0;i < n;i++) {
19
        string s; ll p, t;
20
        cin >> s >> p >> t;
21
        t46[i] = { s,p,t };
22
        mp46[s] = true;
23
    }
24
    ll m;cin >> m;
25
    vector<team>t47(m);
26
    map<string, bool>both;
27
    for (ll i = 0;i < m;i++) {
28
        string s; ll p, t;
29
        cin >> s >> p >> t;
30
        t47[i] = { s,p,t };
31
        if (mp46.count(s)) {
32
            both[s] = true;
33
        }
34
    }
35
    sort(t46.begin(), t46.end());
36
    sort(t47.begin(), t47.end());
37
    string st = "lzr010506";
38
    ll rk = min(n, m);
39
    ll cnt = 1;
40
    for (ll i = 0;i < n;i++) {
41
        if (t46[i].s == st) {
42
            rk = min(cnt, rk);
43
            break;
44
        }
45
        if (both.count(t46[i].s))continue;
46
        cnt++;
47
    }
48
    cnt = 1;
49
    for (ll i = 0;i < m;i++) {
50
        if (t47[i].s == st) {
51
            rk = min(cnt, rk);
52
            break;
53
        }
54
        if (both.count(t47[i].s))continue;
55
        cnt++;
56
    }
57
    cout << rk << "\n";
58
}
59

60
int main() {
61
    int t = 1;
62
    // cin >> t;cin.get();
63
    while (t--)
64
        solve();
65

66
    return 0;
67
}

I-Mirror Maze

补出这题ddl也是死而无憾了。

题意

在 $n\times m$ 的矩阵镜子迷宫里，给出一个点光源，光的传播与镜子的类型\、|、-、/有关（详情戳这）。

提问经过足够长的时间后，这束光被多少个不同的镜子反射过。

数据范围

$1\leq n,m \leq 1000$
$1\leq q\leq 10^5$

思路

考虑到光路可逆，在迷宫中的所有可能存在的光路必然是链或者环，不会出现分叉或者是汇集。考虑数据范围 $1\leq n,m\leq 1000$ 和光的方向有上下左右4个，可以通过记忆化搜索来记录已经搜索过的状态，保证每次搜索的复杂度在 $n\times m$ 以内，总复杂度不超过 $4\times n\times m$ 。

具体搜索方法见代码。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
map<pair<ll, char>, ll>redir;
6

7
void initRedir() {
8
    redir[{1, '|'}] = 1;
9
    redir[{1, '-'}] = 2;
10
    redir[{1, '/'}] = 4;
11
    redir[{1, '\\'}] = 3;
12

13
    redir[{2, '|'}] = 2;
14
    redir[{2, '-'}] = 1;
15
    redir[{2, '/'}] = 3;
16
    redir[{2, '\\'}] = 4;
17

18
    redir[{3, '|'}] = 4;
19
    redir[{3, '-'}] = 3;
20
    redir[{3, '/'}] = 2;
21
    redir[{3, '\\'}] = 1;
22

23
    redir[{4, '|'}] = 3;
24
    redir[{4, '-'}] = 4;
25
    redir[{4, '/'}] = 1;
26
    redir[{4, '\\'}] = 2;
27
}
28

29
bool vis[1005][1005][5] = { false }, visp[1005][1005] = { false };
30
ll n, m;
31
char maz[1005][1005];
32
ll mem[1005][1005][5] = { 0 };
33

34
ll circlelen;
35

36
ll dfs(ll u, ll v, ll dr, ll cnt) {
37
    if (u<1 || u>n || v<1 || v>m) {
38
        // 通过边界出射的点是链型光路
39
        vis[u][v][dr] = false;visp[u][v] = false;
40
        mem[u][v][dr] = cnt;
41
        return cnt;
42
    }
43
    if (vis[u][v][dr]) {
44
        // 因为访问过同样状态结束搜索的是环形光路
45
        vis[u][v][dr] = false;visp[u][v] = false;
46
        circlelen = cnt;
47
        return cnt;
48
    }
49
    if (mem[u][v][dr])return mem[u][v][dr];
50

51
    vis[u][v][dr] = true;
52

53
    ll rdr = redir[{dr, maz[u][v]}];
54

55
    if (!visp[u][v] && dr != rdr) {
56
        cnt++;
57
        visp[u][v] = true;
58
    }
59

60
    if (rdr == 1) cnt = dfs(u - 1, v, 1, cnt);
61
    else if (rdr == 2) cnt = dfs(u + 1, v, 2, cnt);
62
    else if (rdr == 3) cnt = dfs(u, v - 1, 3, cnt);
63
    else cnt = dfs(u, v + 1, 4, cnt);
64

65
    // 回溯时复原状态
66
    vis[u][v][dr] = false;
67
    visp[u][v] = false;
68
    // 若是环形光路，在dfs回溯时mem应该记录为环形路径的长度
69
    if (circlelen)
70
        mem[u][v][dr] = circlelen;
71
    return cnt;
72
}
73

74
void solve() {
75
    cin >> n >> m;
76
    for (ll i = 1;i <= n;i++) {
77
        for (ll j = 1;j <= m;j++) {
78
            cin >> maz[i][j];
79
        }
80
    }
81
    // pre();
82
    ll q;cin >> q;
83
    while (q--) {
84
        ll u, v;string dir;
85
        cin >> u >> v >> dir;
86
        ll dr;
87
        if (dir == "above") { dr = 1;u--; }
88
        else if (dir == "below") { dr = 2;u++; }
89
        else if (dir == "left") { dr = 3; v--; }
90
        else if (dir == "right") { dr = 4; v++; }
91
        circlelen = 0;
92
        ll ans = dfs(u, v, dr, 0);
93
        cout << ans << endl;
94
    }
95
}
96

97
int main() {
98
    initRedir();
99
    int t = 1;
100
    // cin >> t; cin.get();
101
    while (t--)
102
        solve();
103

104
    return 0;
105
}