比赛链接🔗
概述
十分考验码力的一场。
A Bit Common
题面
Given two integers $n$ and $m$, among all the sequences containing $n$ non-negative integers less than $2^m$, you need to count the number of such sequences $A$ that there exists a non-empty subsequence of $A$ in which the bitwise AND of the integers is $1$.
Note that a non-empty subsequence of a sequence $A$ is a non-empty sequence that can be obtained by deleting zero or more elements from $A$ and arranging the remaining elements in their original order.
Since the answer may be very large, output it modulo a positive integer $q$.
The bitwise AND of non-negative integers $A$ and $B$, $A\ \texttt{AND}\ B$ is defined as follows:
- When $A\ \texttt{AND}\ B$ is written in base two, the digit in the $2^d$'s place ($d \ge 0$) is $1$ if those of $A$ and $B$ are both $1$, and $0$ otherwise.
For example, we have $4\ \texttt{AND}\ 6$ = $4$ (in base two: $100\ \texttt{AND}\ 110$ = $100$).
Generally, the bitwise AND of $k$ non-negative integers $p_1, p_2, \ldots, p_k$ is defined as $(\ldots((p_1\ \texttt{AND}\ p_2)\ \texttt{AND}\ p_3)\ \texttt{AND}\ \ldots\ \texttt{AND}\ p_k)$ and we can prove that this value does not depend on the order of $p_1, p_2, \ldots, p_k$.
Input
The only line contains three integers $n$ ($1 \le n \le 5\,000$), $m$ ($1 \le m \le 5\,000$) and $q$ ($1 \le q \le 10^9$).
Output
Output a line containing an integer, denoting the answer.
解题思路
- 从 n 中选 i 个数作为子序列，每个数的二进制形式第一位必须为1，剩下的 m - 1 位中每一位只有所有数在这位为1这种情况不行，及$ 2 ^ i - 1$，在将$2 ^ {m - 1}$个这样的数相乘即为子序列的取法总数。
- 序列中不作为子序列中的 n - i 个数除了第一位为0以外，剩下的 m - 1 位可以任意取0或者1。
- 因为会用到组合数，但是模数并不一定为质数，所以无法使用费马小定理求逆元；观察可以发现n 的最大值为5000，所以可以暴力预处理所有的组合数。
comb[i][k] = (comb[i - 1][k - 1] + comb[i - 1][k]) % q; - 将两种方案数想乘即为答案。
AC代码
#include<bits/stdc++.h>
#define int long long
using ll = long long;
using PII = std::array<int,2>;
using namespace std;
const ll INF = 2E18+10;
typedef long long LL;
int q;
ll power(ll a,ll b,ll m) //快速幂求a^b%m;
{
a%=q;
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%q;
b>>=1;
a=a*a%q;
}
return ans;
}
const int MAXN = 5050;
vector<vector<int>> comb(MAXN + 1, vector<int>(MAXN + 1, 0));
// 计算组合数，取模
void calculate_combinations() {
for (int n = 0; n <= MAXN; ++n) {
for (int k = 0; k <= n; ++k) {
if (k == 0 || k == n) {
comb[n][k] = 1; // C(n, 0) = C(n, n) = 1
} else {
comb[n][k] = (comb[n - 1][k - 1] + comb[n - 1][k]) % q; // 递推关系式，取模
}
}
}
}
// 查询组合数，取模
int get_combination(int n, int k) {
if (k > n || k < 0) {
return 0; // 如果 k 超过 n 或者小于 0，则返回 0
}
return comb[n][k];
}
void SINGLE_TEST()
{
int n, m;
cin>> n >> m >> q;
calculate_combinations();
ll ans = 0;
for(int i = 1;i <= n;i ++ ) {
ll res = get_combination(n, i) * power(power(2, i, q) - 1, m - 1, q) % q;
ll sum = power(2, m - 1, q) % q;
res = res * power(sum, n - i, q) % q;
ans += res;
ans %= q;
}
cout<< ans <<"\n";
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int SAMPLES = 1;
// cin>>SAMPLES;
while(SAMPLES--) SINGLE_TEST();
}B A Bit More Common
题面
Given two integers $n$ and $m$, among all the sequences containing $n$ non-negative integers less than $2^m$, you need to count the number of such sequences $A$ that there exists two different non-empty subsequences of $A$ in each of which the bitwise AND of the integers is $1$.
Note that a non-empty subsequence of a sequence $A$ is a non-empty sequence that can be obtained by deleting zero or more elements from $A$ and arranging the remaining elements in their original order. Two subsequences are different if they are composed of different locations in the original sequence.
Since the answer may be very large, output it modulo a positive integer $q$.
The bitwise AND of non-negative integers $A$ and $B$, $A\ \texttt{AND}\ B$ is defined as follows:
- When $A\ \texttt{AND}\ B$ is written in base two, the digit in the $2^d$'s place ($d \ge 0$) is $1$ if those of $A$ and $B$ are both $1$, and $0$ otherwise.
For example, we have $4\ \texttt{AND}\ 6$ = $4$ (in base two: $100\ \texttt{AND}\ 110$ = $100$).
Generally, the bitwise AND of $k$ non-negative integers $p_1, p_2, \ldots, p_k$ is defined as $(\ldots((p_1\ \texttt{AND}\ p_2)\ \texttt{AND}\ p_3)\ \texttt{AND}\ \ldots\ \texttt{AND}\ p_k)$ and we can prove that this value does not depend on the order of $p_1, p_2, \ldots, p_k$.
INPUT
The only line contains three integers $n$ ($1 \le n \le 5\,000$), $m$ ($1 \le m \le 5\,000$) and $q$ ($1 \le q \le 10^9$).
OUTPUT
Output a line containing an integer, denoting the answer.
解题思路
AC代码
C Sum of Suffix Sums
题面
Given an array which is initially empty, you need to perform $q$ operations:
- Given two non-negative integers $t$ and $v$, take out the element from the end of the array for $t$ times and then append $v$ to the end of the array. It is guaranteed that $t$ does not exceed the length of the array before this operation.
After each operation, let $a_1, a_2, \ldots, a_n$ be the current array, find the sum of $s_1, s_2, \ldots, s_n$, where $s_i = a_i + a_{i+1} + \ldots + a_n$ is the sum of the suffix starting from position $i$.
Since the answers may be very large, output them modulo $1\,000\,000\,007$.
INPUT
The first line contains an integer $q$ ($1 \le q \le 5 \times 10^5$), denoting the number of operations.
Each of the following $q$ lines contains two non-negative integers $t$ and $v$ ($0 \le v \le 10^9$), describing an operation, where $t$ does not exceed the length of the array before this operation.
OUTPUT
Output $q$ lines, each of which contains an integer, denoting the answer.
解题思路
- 记当前序列为 a1, a2, . . . , an
- 不难发现 ai 会出现在所有起始位置 ≤ i 的后缀和里，在总和里出现 i 次
- 总和就是 ∑n i=1 i × ai，直接维护即可
- 时间复杂度是 O(q)
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
ll a[N];
ll res = 1;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll q; cin >> q;
while(q -- ) {
ll t, v; cin >> t >> v;
res -= t;
a[res] = res * v;
res ++ ;
a[res - 1] = (a[res - 1] + a[res - 2]) % mod;
cout << a[res - 1] << endl;
}
return 0;
}H World Finals
题面
The ICPC World Finals are coming. Due to some reasons, the 46th and 47th World Finals will be held simultaneously. For the teams qualified in both competitions, they should choose one to take part in.
As we know, lzr010506's team is double-qualified and should make a choice. To make a wiser choice, lzr010506 looked up the qualified lists for two competitions and trained a magic model to predict the results for all participants among the two competitions. Moreover, a result contains the number of solved problems and the time penalty. The more solved problems, the better the result is, and if two teams solved the same number of problems, the result with the lower time penalty is better.
Now, lzr010506 wants to know the best possible ranking if the actual results are all the same as predicted and that the competition choices of the double-qualified teams can be arbitrarily arranged by him.
INPUT
The first line contains one integer $n\,(1 \le n \le 10^5)$, denoting the number of teams qualified in the 46th World Finals.
Next $n$ lines each contain one string $S\,(1 \le |S| \le 10)$ and two integers $p,t\,(1 \le p,t \le 10^9)$, denoting the name, the predicted number of solved problems, and time penalty of one team in the 46th World Finals respectively.
Next one line contains one integer $m\,(1 \le m \le 10^5)$, denoting the number of teams qualified in the 47th World Finals.
Next $m$ lines each contain one string $S\,(1 \le |S| \le 10)$ and two integers $p,t\,(1 \le p,t \le 10^9)$, denoting the name, the predicted number of solved problems, and time penalty of one team in the 47th World Finals respectively.
It is guaranteed that:
· the team names only contain digits and English letters;
· the team names in one competition are different from each other;
· no two teams have the same predicted number of solved problems and the time penalty simultaneously in one competition;
· the same names among two qualified name lists refer to the same team in real;· lzr010506 appears in both two qualified name lists.
OUTPUT
Output one line containing one integer, denoting the best possible ranking of lzr010506's team.
解题思路
- 减去两边同时出现排名在前面的即为最小值
AC代码
#include<bits/stdc++.h>
#define int long long
using ll = long long;
using PII = std::array<int,2>;
using namespace std;
const ll INF = 2E18+10;
#ifdef __clang__
template<typename T>
inline int my_lg(T n) {
return (n > 0) ? static_cast<int>(log2(n)) : -1;
}
#define __lg my_lg
#define __gcd gcd
#endif
#ifndef ONLINE_JUDGE
#include "_debug.h"
#define EL std::cout<<"\n";
#define COUT(ITEM) std::cout<<#ITEM<<"="<<ITEM<<'\n';
#define CERR(ITEM) std::cerr<<#ITEM<<"="<<ITEM<<'\n';
#endif
// struct cmp{bool operator()(const int & x, const int &y) const{ return x<y; }};
const int N = 2E6 + 10;
void SINGLE_TEST()
{
int n,m;
cin>>n;
map<string,PII> a,b;
int ans=INF;
vector<string> s,w;
vector<int> s1,s2,w1,w2;
int t1,t2;
int z1,z2;
map<string,bool> vis1,vis2;
for(int i=1;i<=n;i++){
string ss;cin>>ss;
int ss1,ss2;
cin>>ss1>>ss2;
s.push_back(ss);
s1.push_back(ss1);
s2.push_back(ss2);
if(ss=="lzr010506"){
t1=ss1;
t2=ss2;
}
vis1[ss]=true;
}
cin>>m;
for(int i=1;i<=m;i++){
string ss;cin>>ss;
int ss1,ss2;
cin>>ss1>>ss2;
w.push_back(ss);
w1.push_back(ss1);
w2.push_back(ss2);
if(ss=="lzr010506"){
z1=ss1;
z2=ss2;
}
vis2[ss]=true;
}
int p1=0,p2=0;
for(int i=0;i<n;i++){
if(s[i]=="lzr010506") continue;
if(s1[i]>t1 || s1[i]==t1 && s2[i]<t2){
p1++;
if(vis2[s[i]]){
p1--;
}
}
}
for(int i=0;i<m;i++){
if(w[i]=="lzr010506") continue;
if(w1[i]>z1 || w1[i]==z1 && w2[i]<z2){
p2++;
if(vis1[w[i]]){
p2--;
}
}
}
cout<<min(p1,p2)+1<<"\n";
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int SAMPLES = 1;
// cin>>SAMPLES;
while(SAMPLES--) SINGLE_TEST();
}I Mirror Maze
题面
There is an $n\times m$ mirror maze, where there is a mirror on each grid. The mirrors are in one of the following four types:
- \`\`-'', the light from above or below will be reflected back, the light from left or right will continue going forward without being reflected, respectively;
- \`\`|'', the light from left or right will be reflected back, the light from above or below will continue going forward without being reflected, respectively;
- \`\`/'', the light from left, right, above, below will be reflected to go above, below, left, right, respectively;
- \`\`$\backslash$'', the light from left, right, above, below will be reflected to go below, above, right, left, respectively.
Now there are $q$ light sources. Little G, the believer of the light, wants to know the numbers of different mirrors the emitted light will be reflected by within sufficient time for each light source.
INPUT
The first line contains two integers $n,m\,(1 \le n,m \le 1\,000)$, denoting the size of the mirror maze.
Each of the following $n$ lines contains a string of length $m$, where the $j$-th character in the $i$-th line $S_{i,j}\,(S_{i,j} \in \{|, -, /, \backslash\})$ denotes the mirror on grid $(i,j)$.
The next line contains an integer $q\,(1 \le q \le 10^5)$, denoting the number of light sources.
Each of the following $q$ lines contains two integers $u\,(1 \le u \le n)$, $v\,(1 \le v \le m)$ and a string $dir\,(dir \in \{above, below, left, right\})$, denoting that a light source is on grid $(u,v)$ and emits light going along the $dir$ direction. Specifically, the light will not be influenced by the mirror on grid $(u,v)$ initially.
OUTPUT
Output $q$ lines each containing one integer, denoting the number of different mirrors the emitted light will be reflected by within sufficient time for each light source.
解题思路
- 预处理整张图，然后o(1)输出答案。
- 注意环与不折射问题
- 强大的码力
AC代码
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::string> s(n);
for (int i = 0; i < n; i++) {
std::cin >> s[i];
}
auto V = [&](int x, int y) {
return x * (m + 1) + y;
};
auto H = [&](int x, int y) {
return n * (m + 1) + x * m + y;
};
const int N = n * (m + 1) + (n + 1) * m;
std::vector<std::array<std::pair<int, int>, 2>> adj(N, {std::make_pair(-1, -1), std::make_pair(-1, -1)});
std::vector<std::array<int, 2>> tot(N);
auto addEdge = [&](int u, int v, int du, int dv, int w) {
adj[u][du] = {v * 2 + dv, w};
adj[v][dv] = {u * 2 + du, w};
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int mir = i * m + j;
if (s[i][j] == '-') {
addEdge(V(i, j), V(i, j + 1), 1, 0, -1);
addEdge(H(i, j), H(i, j), 1, 1, mir);
addEdge(H(i + 1, j), H(i + 1, j), 0, 0, mir);
} else if (s[i][j] == '|') {
addEdge(V(i, j), V(i, j), 1, 1, mir);
addEdge(V(i, j + 1), V(i, j + 1), 0, 0, mir);
addEdge(H(i, j), H(i + 1, j), 1, 0, -1);
} else if (s[i][j] == '/') {
addEdge(V(i, j), H(i, j), 1, 1, mir);
addEdge(V(i, j + 1), H(i + 1, j), 0, 0, mir);
} else {
addEdge(V(i, j), H(i + 1, j), 1, 0, mir);
addEdge(V(i, j + 1), H(i, j), 0, 1, mir);
}
}
}
std::vector<bool> vis(N);
std::vector<int> tm(n * m, -1);
for (int x = 0; x < N; x++) {
if (adj[x][0].first == -1 || adj[x][1].first == -1) {
int a = x;
int d = (adj[a][1].first == -1);
int sum = 0;
while (a != -1) {
vis[a] = true;
tot[a][d] = sum;
auto [b, w] = adj[a][d ^ 1];
if (w != -1) {
sum += (tm[w] != x);
tm[w] = x;
}
if (b == -1) {
a = -1;
} else {
d = b % 2;
a = b / 2;
}
}
}
}
for (int x = 0; x < N; x++) {
if (vis[x]) {
continue;
}
int a = x;
int d = 0;
int sum = 0;
do {
vis[a] = true;
auto [b, w] = adj[a][d ^ 1];
if (w != -1) {
sum += (tm[w] != x);
tm[w] = x;
}
d = b % 2;
a = b / 2;
} while (a != x || d != 0);
do {
tot[a][0] = tot[a][1] = sum;
auto [b, w] = adj[a][d ^ 1];
d = b % 2;
a = b / 2;
} while (a != x || d != 0);
}
int q;
std::cin >> q;
while (q--) {
int x, y;
std::string dir;
std::cin >> x >> y >> dir;
int d;
x--;
y--;
int a;
if (dir == "above") {
a = H(x, y);
d = 0;
} else if (dir == "below") {
a = H(x + 1, y);
d = 1;
} else if (dir == "left") {
a = V(x, y);
d = 0;
} else {
a = V(x, y + 1);
d = 1;
}
std::cout << tot[a][d] << "\n";
}
return 0;
}