A Bit Common

题目大意

给定序列的长度$n$，每个数的二进制位数$m$，模数$q$，问你有多少个序列满足这个序列（至少）存在一个子序列使得它们的按位与的结果为$1$。

解题思路

显然，要找到一个序列满足至少存在一个子序列按位与为$1$，那么对于二进制最低位为$0$的一定不选，最低位为$1$的选一定更容易得到$1$。枚举有$i$个数($n$个数中选$i$个，$C_n^i$)二进制位最低位为$1$，考虑用这$i$个数能按位与得到$1$，则对于每一个除了最低位的二进制位都需要满足在这$i$个数中至少有一个数该位为$0$(考虑每一个二进制位，总共$2^i$种情况，减去全$1$情况，即$2^i -1$，共$m-1$位，结合起来即$(2^i-1)^{m-1}$)。对于二进制位最低位为$0$的情况，由于题意所求子序列一定不会包含这个数，所以非最低位任意填不会对结果造成影响($2^{(n-i)(m-1)}$)。

所以最终式子为$C_n^i(2^i-1)^{m-1}2^{(n-i)(m-1)}$，$i$从$1$到$n$求和。

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;
const int N = 5010;
int n, m, mod;

long long qpow(long long a,long long b,long long p){
    a%=p;
    long long res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

int c[N][N];

void solve(){
    cin >> n >> m >> mod;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = (ans + c[n][i] * qpow((qpow(2, i, mod) - 1 + mod) % mod, m - 1, mod) % mod * qpow(2, (n - i) * (m - 1), mod) % mod) % mod;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

A Bit More Common

题目大意

给定序列的长度$n$，每个数的二进制位数$m$，模数$q$，问你有多少个序列满足这个序列（至少）存在两个不同的子序列使得它们的按位与的结果为$1$。

解题思路

对比上一题，本题求的要求两个不同的子序列按位与为$1$，考虑容斥，用上题答案减去仅存在一个子序列它们的按位与结果为$1$。

如何计算仅存在一个子序列他们按位与结果为$1$的方案数？

思考需要满足这个条件的性质，记每个最低位为$1$的数构成的集合为$S$，对于$S$中每个元素都必须满足，至少存在一个非最低位在$S$中只有该数为$0$，这样就保证了不选这个数那么按位与的结果一定会有非最低位为$1$，因为只有这个数能让某个非最低位为$0$，这里我们记这样的位叫做特殊位。

令$dp[i][j]$表示$i$个数总共有$j$个特殊位的方案数，考虑转移，考虑当前情况下最新加进来的特殊位有$i$个数可以对应，即有$i$种情况，如果删掉这个特殊位，可能仍有$i$个数即每个数仍还有特殊位，也可能剩下$i-1$个数删掉的哪个特殊位为对应数唯一的特殊位，状态转移方程$dp[i][j]=i\times (dp[i][j-1],dp[i-1][j-1])$。

记选了$k$个二进制最低位为$1$的数，对应了$t$个特殊位。对于最低位为$1$的数非特殊位，需要保证该位至少有一个$0$且不是特殊位，共有$m-1-t$个非特殊位且非最低位，而最低位为$0$的数非最低位同样任意选，方案数$C_n^k 2^{(n-k)(m-1)} C_{m-1}^t dp[k][t] {(2^k-k-1)}^{m-1-t}$，$k$从$2$到$n$求和，$t$从$k$到$m-1$求和，对于$k=1$的情况单独考虑，

对于最低位为$1$的数其它位必须都为$0$，其它数的非最低位任意选。

由于这题比较卡常，循环内的快速幂可以通过循环顺序优化掉，时间复杂度$O(n^2)$

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;
const int N = 5010;
int n, m, mod;

long long qpow(long long a,long long b,long long p){
    a%=p;
    long long res=1%p;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

int c[N][N];
int dp[N][N];

void add(int& a, int b) {
    a += b;
    if(a >= mod) a -= mod;
}

void solve(){
    cin >> n >> m >> mod;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    
    int ans1 = 0;
    vector<int> tt2(n + 1), p2(n + 1);
    p2[0] = 1 % mod;
    for(int i = 1; i <= n; i++) {
        tt2[i] = qpow(2, (n - i) * (m - 1), mod);
    }
    for(int i = 1; i <= n; i++) {
        p2[i] = p2[i - 1] * 2 % mod;
    }
    for(int i = 1; i <= n; i++) {
        ans1 = (ans1 + c[n][i] * qpow((p2[i] - 1 + mod) % mod, m - 1, mod) % mod * tt2[i] % mod) % mod;
    }
    int ans2 = c[n][1] * qpow(2, (n - 1) * (m - 1), mod) % mod;
    // cout << ans2 << '\n';
    dp[0][0] = 1;
    for(int i = 1; i <= 5000; i++) {
        for(int j = 1; j <= 5000; j++) {
            dp[i][j] = i * (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
        }
    }
    // cout << "DWJAIO:" << dp[2][2] << '\n';
    for(int k = 2; k <= n; k++) {
        int t1 = c[n][k];
        int t2 = tt2[k];
        int t5 = (p2[k] - k - 1 + mod) % mod;
        int t6 = 1;
        for(int t = m - 1; t >= k; t--) {
            int t3 = c[m - 1][t];
            int t4 = dp[k][t];
            int add = t1 * t2 % mod * t3 % mod * t4 % mod * t6 % mod;
            t6 = t6 * t5 % mod;
            ans2 += add;
            if(ans2 > mod) ans2 -= mod;
        }
    }

    // for(int k = 2; k <= n; k++) {
    //     int t1 = c[n][k];
    //     int t2 = tt2[k];
    //     int t5 = ((p2[k] - k - 1) % mod + mod) % mod;
    //     int t6 = 1;
    //     for(int t = m - 1; t >= k; t--) {
    //         int t3 = c[m - 1][t];
    //         int t4 = dp[k][t];
    //         t6 = t6 * t5 % mod;
    //         int add = t1 * t2 % mod * t3 % mod * t4 % mod * t6 % mod;
    //         ans2 += add;
    //         if(ans2 >= mod) ans2 -= mod;
    //     }
    // }
    // cout << ans1 << '\n';
    cout << (ans1 - ans2 + mod) % mod << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

Sum of Suffix Sums

题目大意

给定$q$次操作，每次操作给你两个数$t,v$，表示先删掉序列中的$t$个数再在最后插入大小为$v$的数的操作，每次操作询问你此时序列的所有后缀和的和。

解题思路

令序列为$\lbrace a_1,a_2,\dots,a_k \rbrace$，那么所有后缀和的和即$a_1+a_2\times 2+\dots+a_k\times k$，考虑维护当前答案，每次删除最后一个元素答案减去删去元素与删前元素个数的积，添加一个元素答案加上加入的元素与加入后元素个数的积，模拟即可。

注意size_t类型类似unsigned int没有负数，用int减去size_t或用size_t减去int要注意出现小于0的情况，此时值会变成正无穷，再取模答案已经不正确了，可以用(int)vector.size()来避免int与size_t运算出现错误。

参考代码

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
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> pll;
string yes = "YES";
string no = "NO";
constexpr int mod = 1e9 + 7;
void solve()
{
    int q;
    cin >> q;
    vector<int>s;
    // s.push_back(1);
    // cout << (1LL - s.size() * 10LL) << '\n';
    int ans = 0;
    while(q--)
    {
        int t, x;
        cin >> t >> x;
        while(t--)
        {
            int xx = s.back();
            ans = ((ans - (int)s.size() * xx) % mod + mod) % mod;
            s.pop_back();
        }
        s.push_back(x);
        ans = (ans + (int)s.size() * s.back() % mod) % mod;
        cout << ans << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
}

World Finals

题目大意

以46届和47届的world finals为背景，由于这两场world final同时进行，两个队都可以参加的队伍只能选择一队参加。题中给出两场world final各队伍的预测做题情况，问你如果同时能参加两场比赛的队伍可以由你任意分配，问“lzr010506”这个队的可以达到的最好的排名。

解题思路

签到题，分别模拟lzr010506参加46届，能参加两场比赛的队伍选择参加47届，或lzr010506参加47届能参加两场比赛的队伍选择参加46届这两种情况。

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;

struct Node{
    string s;
    int p, t;
    bool operator<(const Node& w) const {
        if(p != w.p) return p > w.p;
        return t < w.t;
    }
};

void solve(){
    int n;
    cin >> n;
    map<string, int> cnt;
    vector<Node> v1, v2;
    for(int i = 0; i < n; i++) {
        string s;
        int p, t;
        cin >> s >> p >> t;
        cnt[s]++;
        v1.push_back({s, p, t});
    }
    int m;
    cin >> m;
    for(int i = 0; i < m; i++) {
        string s;
        int p, t;
        cin >> s >> p >> t;
        cnt[s]++;
        v2.push_back({s, p, t});
    }
    int ans = INF;
    {
        vector<Node> v;
        for(auto x: v1) {
            if(x.s == "lzr010506" || cnt[x.s] != 2) {
                v.push_back(x);
            }
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++) {
            if(v[i].s == "lzr010506") {
                ans = min(ans, i + 1);
                break;
            }
        }
    }
    {
        vector<Node> v;
        for(auto x: v2) {
            if(x.s == "lzr010506" || cnt[x.s] != 2) {
                v.push_back(x);
            }
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++) {
            if(v[i].s == "lzr010506") {
                ans = min(ans, i + 1);
                break;
            }
        }
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

Mirror Maze

题目大意

给定$n\times m$的镜子迷宫，每个位置都有一个镜子，共有四种镜子‘-’、’|’、’/‘、’\\’，分别可以反射从一定方向的来的光，给你$q$次询问，每次问你从该点出发向上下左右某个方向射出的光会反射多少面镜子，注意过程中遇到的同一个镜子只算一次。

解题思路

容易发现，只有两种情况。一种情况是这个光反射有限次数后会出去，另一种情况会形成环。考虑预处理每个位置向四周发射光的答案，对于前者，我们可以枚举所有从外面射向最外围一圈的情况，如左边一列的点分别枚举从外面向右射向这些点，上边一行的点分别枚举从外面向下射入这些点。每次记录过程中经过的镜子数量，并根据光路可逆的原理记录到预处理的数组中。剩下的未记录的情况即环，我们每次跑一遍环记录该环总数分别赋值即可。个人建议用$dfs$写更加方便，$dfs$可以同时处理刚遍历到该点的情况和该点以后的点都处理好后再处理该点两种情况。如环的情况可以在$dfs$函数中递归下一个点代码前处理计数，递归下一个点代码后赋值答案。

参考代码

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 0;

const int N = 1010;
int n, m;
vector<string> s(N);
int ans[N][N][4];
int to[N][N][4];

int fan(int d) {
    return d ^ 2;
}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int vis[N][N], sum;
vector<PII> rec;
bool fhuan;

int getto(int x, int y, int from) {
    int to = fan(from);
    if(s[x][y] == '/') {
        if(from == 0) {
            to = 1;
        }else if(from == 1) {
            to = 0;
        }else if(from == 2) {
            to = 3;
        }else if(from == 3) {
            to = 2;
        }else{
            assert(0);
        }
    }else if(s[x][y] == '\\') {
        if(from == 0) {
            to = 3;
        }else if(from == 1) {
            to = 2;
        }else if(from == 2) {
            to = 1;
        }else if(from == 3) {
            to = 0;
        }else{
            assert(0);
        }
    }else if(s[x][y] == '-') {
        if(from == 0) {
            
        }else if(from == 1) {
            to = 1;
        }else if(from == 2) {

        }else if(from == 3) {
            to = 3;
        }else{
            assert(0);
        }
    }else if(s[x][y] == '|') {
        if(from == 0) {
            to = 0;
        }else if(from == 1) {

        }else if(from == 2) {
            to = 2;
        }else if(from == 3) {

        }else{
            assert(0);
        }
    }else{
        assert(0);
    }
    return to;
}
int stx = -1, sty = -1, stfrom = -1, cnt = 0;
void dfs(int x, int y, int from) {
    // cerr << x << ' ' << y << ' ' << from << ' ' << stx << ' ' << sty << ' ' << stfrom << '\n';
    // cerr << x << ' ' << y << ' ' << from << '\n';
    if(x < 1 || x > n || y < 1 || y > m) {
        assert(fhuan == 0);
        return;
    }
    if(stx == x && sty == y && stfrom == from && ++cnt == 2) {
        assert(fhuan == 1);
        return;
    }
    int tox = x, toy = y, to = getto(x, y, from);

    if(!fhuan) ans[x][y][from] = sum;
    tox += dx[to], toy += dy[to];
    if(to != fan(from)) {
        if(++vis[x][y] == 1) {
            rec.push_back({x, y});
            sum++;
        }
    }
    dfs(tox, toy, fan(to));
    if(fhuan) ans[x][y][from] = sum;
}

void solve(int x, int y, int from) {
    if(fhuan) {
        stx = x, sty = y, stfrom = from, cnt = 0;
    }
    dfs(x, y, from);
    sum = 0;
    for(auto [a, b]: rec) {
        // cerr << a << ' ' << b << '\n';
        vis[a][b] = 0;
    }
    rec.clear();
}

void solve(){
    memset(ans, -1, sizeof ans);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = ' ' + s[i];
    }
    // fhuan = 1;
    // solve(1, 2, 2);
    // cout << "ans:" << ans[1][2][2] << '\n';
    // return;
    for(int i = 1; i <= n; i++) {
        solve(i, 1, 2);
        solve(i, m, 0);
    }
    for(int j = 1; j <= m; j++) {
        solve(1, j, 3);
        solve(n, j, 1);
    }
    // cerr << "huanhuan\n\n";
    fhuan = 1;

    // solve(1, 1, 0);


    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k < 4; k++) {
                if(ans[i][j][k] == -1) {
                    // cerr << "DOWJAID: " << i << ' ' << j << ' ' << k << '\n';
                    solve(i, j, k);
                }
            }
        }
    }
    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= m; j++) {
    //         cerr << vis[i][j] << " \n"[j == m];
    //     }
    // }

    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= m; j++) {
    //         cout << ans[i][j][2] << " \n"[j == m];
    //     }
    // }
    map<string, int> mp{{"right", 0}, {"below", 1}, {"left", 2}, {"above", 3}};
    int q;
    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        string t;
        cin >> t;
        cout << ans[x][y][mp[t]] << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}