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

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

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

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

https://img.dodolalorc.cn/i/2024/07/17/66978bf423ad6.png

如图按位分析,对于一个长度为$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
 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5050;

ll qpow(ll a, ll b, ll m) {
    // 快速幂
    ll res = 1;
    while (b) {
        if (b & 1)res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}

ll C[maxn][maxn];

void solve() {
    ll n, m, q;
    cin >> n >> m >> q;
    C[0][0] = 1;
    for (ll i = 1;i <= n;i++) {
        C[i][0] = 1, C[i][i] = 1;
        for (ll j = 1;j < i;j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % q;
        }
    }
    ll ans = 0;
    for (ll k = 1;k <= n;k++) {
        ll tmp = C[n][k];
        ll x = (qpow(2, n, q) - qpow(2, n - k, q) + q) % q;
        tmp *= qpow(x, m - 1, q);
        tmp %= q;
        ans = (ans + tmp + q) % q;
    }
    cout << ans % q << "\n";
}

int main() {
    int _ = 1;
    // cin >> _;cin.get();
    while (_--)
        solve();

    return 0;
}

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

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

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

满足只有1个子序列的组合数所代表的情况是这样的: $$ let:k=3\\ 101111\\ 010101\\ 111011 $$ 需要满足每一个竖列至少有一个特殊的$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
 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
ll qpow(ll a, ll b, ll m) {
    // 快速幂
    ll res = 1;
    a %= m;
    while (b) {
        if (b & 1)res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}

ll C[maxn][maxn];
ll f[maxn][maxn];

void solve() {
    ll n, m, q;
    cin >> n >> m >> q;
    C[0][0] = 1ll;
    for (ll i = 1;i <= 5000;i++) {
        C[i][0] = 1, C[i][i] = 1;
        for (ll j = 1;j <= 5000;j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % q;
        }
    }
    ll ans = 0;
    for (ll k = 1;k <= n;k++) {
        ll tmp = C[n][k];
        ll x = (qpow(2ll, n, q) - qpow(2ll, n - k, q) + q) % q;
        tmp *= qpow(x, m - 1ll, q);
        tmp %= q;
        ans = (ans + tmp + q) % q;
    }

    ll res = qpow(2ll, (n - 1) * (m - 1) % q, q) * n % q;
    // 存在1个子序列AND=1的,减去只有1个子序列AND=1的
    f[0][0] = 1ll;
    for (ll i = 1;i <= 5000;i++) {
        for (ll j = i;j <= 5000;j++) {
            f[i][j] = i * ((f[i - 1][j - 1] + f[i][j - 1]) % q) % q;
        }
    }
    for (ll k = 2;k <= n;k++) {
        ll tmp = qpow(2ll, (n - k) * (m - 1) % q, q) % q * C[n][k] % q;
        ll tmp2 = (qpow(2ll, k, q) - 1ll - k + q) % q;
        ll cur = 1ll;
        for (ll t = m - 1;t >= k;t--) {
            res = (res + f[k][t] * cur % q * C[m - 1][t] % q * tmp % q) % q;
            cur = tmp2 * cur % q;
        }
    }

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

维护一个初始为空的非负整数序列,支持$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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
    ll q;cin >> q;
    vector<ll>a;
    ll tot = 0;
    while (q--) {
        ll t, v;cin >> t >> v;
        v %= mo;
        for (ll i = 0;i < t;i++) {
            if (a.empty())break;
            ll x = a.back();
            tot -= x * a.size();
            tot = (tot + mo) % mo;
            a.pop_back();
        }
        a.push_back(v);
        ll n = a.size() % mo;
        tot = (tot + v * n % mo + mo) % mo;
        cout << tot << "\n";
    }
}

签到题。

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

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

  • $1 \leq number of teams \leq 105$

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

 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct team {
    string s;
    ll p, t;
    bool operator<(const team& other)const {
        if (other.p == p)return other.t > t;
        return other.p < p;
    }
};

void solve() {
    ll n;cin >> n;
    vector<team>t46(n);
    map<string, bool>mp46;
    for (ll i = 0;i < n;i++) {
        string s; ll p, t;
        cin >> s >> p >> t;
        t46[i] = { s,p,t };
        mp46[s] = true;
    }
    ll m;cin >> m;
    vector<team>t47(m);
    map<string, bool>both;
    for (ll i = 0;i < m;i++) {
        string s; ll p, t;
        cin >> s >> p >> t;
        t47[i] = { s,p,t };
        if (mp46.count(s)) {
            both[s] = true;
        }
    }
    sort(t46.begin(), t46.end());
    sort(t47.begin(), t47.end());
    string st = "lzr010506";
    ll rk = min(n, m);
    ll cnt = 1;
    for (ll i = 0;i < n;i++) {
        if (t46[i].s == st) {
            rk = min(cnt, rk);
            break;
        }
        if (both.count(t46[i].s))continue;
        cnt++;
    }
    cnt = 1;
    for (ll i = 0;i < m;i++) {
        if (t47[i].s == st) {
            rk = min(cnt, rk);
            break;
        }
        if (both.count(t47[i].s))continue;
        cnt++;
    }
    cout << rk << "\n";
}

int main() {
    int t = 1;
    // cin >> t;cin.get();
    while (t--)
        solve();

    return 0;
}

补出这题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
  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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

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

void initRedir() {
    redir[{1, '|'}] = 1;
    redir[{1, '-'}] = 2;
    redir[{1, '/'}] = 4;
    redir[{1, '\\'}] = 3;

    redir[{2, '|'}] = 2;
    redir[{2, '-'}] = 1;
    redir[{2, '/'}] = 3;
    redir[{2, '\\'}] = 4;

    redir[{3, '|'}] = 4;
    redir[{3, '-'}] = 3;
    redir[{3, '/'}] = 2;
    redir[{3, '\\'}] = 1;

    redir[{4, '|'}] = 3;
    redir[{4, '-'}] = 4;
    redir[{4, '/'}] = 1;
    redir[{4, '\\'}] = 2;
}

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

ll circlelen;

ll dfs(ll u, ll v, ll dr, ll cnt) {
    if (u<1 || u>n || v<1 || v>m) {
        // 通过边界出射的点是链型光路
        vis[u][v][dr] = false;visp[u][v] = false;
        mem[u][v][dr] = cnt;
        return cnt;
    }
    if (vis[u][v][dr]) {
        // 因为访问过同样状态结束搜索的是环形光路
        vis[u][v][dr] = false;visp[u][v] = false;
        circlelen = cnt;
        return cnt;
    }
    if (mem[u][v][dr])return mem[u][v][dr];

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

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

    if (!visp[u][v] && dr != rdr) {
        cnt++;
        visp[u][v] = true;
    }

    if (rdr == 1) cnt = dfs(u - 1, v, 1, cnt);
    else if (rdr == 2) cnt = dfs(u + 1, v, 2, cnt);
    else if (rdr == 3) cnt = dfs(u, v - 1, 3, cnt);
    else cnt = dfs(u, v + 1, 4, cnt);

    // 回溯时复原状态
    vis[u][v][dr] = false;
    visp[u][v] = false;
    // 若是环形光路,在dfs回溯时mem应该记录为环形路径的长度
    if (circlelen)
        mem[u][v][dr] = circlelen;
    return cnt;
}

void solve() {
    cin >> n >> m;
    for (ll i = 1;i <= n;i++) {
        for (ll j = 1;j <= m;j++) {
            cin >> maz[i][j];
        }
    }
    // pre();
    ll q;cin >> q;
    while (q--) {
        ll u, v;string dir;
        cin >> u >> v >> dir;
        ll dr;
        if (dir == "above") { dr = 1;u--; }
        else if (dir == "below") { dr = 2;u++; }
        else if (dir == "left") { dr = 3; v--; }
        else if (dir == "right") { dr = 4; v++; }
        circlelen = 0;
        ll ans = dfs(u, v, dr, 0);
        cout << ans << endl;
    }
}

int main() {
    initRedir();
    int t = 1;
    // cin >> t; cin.get();
    while (t--)
        solve();

    return 0;
}

相关内容