提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
A. A Bit Common
题意： 给出n和m两个整数（n , m <= 5000），计算符合下列条件的序列A的个数：
· 序列A长n，每个元素小于2^m
· 存在某个非空子序列满足按位与的值为1
注意： 结果可能很大，输出模 p 后的结果
样例：
case1:
输入：
2 3 998244353
输出：
17
case2：
输入：
5000 5000 998244353
输出：
2274146
分析：
将序列中的每个元素看成二进制形式，则可将序列拆成n行m列的矩阵形式，每一行是一个元素，每
个元素最多m个二进制位，每位只能取0或1。如n = 2 ， m = 3时的情况：
二进制位： 3 2 1
第一行（第一个元素）： [ ] [ ] [ ]
第二行（第二个元素）： [ ] [ ] [ ]
分析可得，若要存在子序列按位与值为1，则需要此子序列中每个元素第一位取 1 ，其他位每一位至少存在一个元素此位为 0 ，才能在按位与的条件下得到第一位的值为 1 其他位为 0 最终结果为 1。
如此我们考虑从1到n枚举第一位为1的元素个数，计算每个情况下的符合条件序列A个数，计算方法：
若第一位为1的元素个数为 i ,我们选出 i 个位置，使其第一位为 1 ，C(n,i) （此处C意为组合数 ，C(n,i）为n个元素取 i 个)，这 i 个元素保证除第一位为 1 ，后m-1位至少存在一个元素取 0 ，而每一位至少一个元素取 0 其他位任取即转化成长度为 i 的序列中求得至少 1 位取 0 的排列问题，即为1 + 2 + …… + 2^(i-1) = x , 可知后m-
1位的情况全部一样，则后m-1位总情况数为 x ^ (m-1) ， 如此有 i 个元素第一位为1的情况下的子序列总排列处理完毕此部分贡献值为 C(n,i) * x ^ (m-1) ，此情况已经保证必定存在子序列按位与值为1， 再乘上第一位为 0 后 m-1 位任取的贡献值—— 2 ^ ((n-i)(m-1))即为 i 出的贡献值，累加 i 从1到 n 的情况做好取模则为最后答案。
幂运算结果过大，且需要取模，运用快速幂处理，组合数数据范围小，直接利用公式预处理存入数组即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 3;
int n , m , p;
long long c[N][N];
long long sum[N];
long long ksm(long long a , long long x) {
long long r = 1;
while(x) {
if(x & 1) r = r * a % p;
x >>= 1;
a = a * a % p;
}
return r;
}
void init(){
//预处理组合数c数组信息
for(int i = 0;i <= 5000;i ++){
c[i][0] = 1;
}
for(int i = 1;i <= 5000;i ++){
for(int j = 1;j <= i;j ++){
c[i][j] = (c[i-1][j-1]+c[i-1][j]) % p;
}
}
预处理1+……+2^(i-1)的值
for(int i=1;i<=5000;i++){
sum[i]=(sum[i-1]+ksm(2LL,i-1LL)) % p;
}
}
void solve() {
cin >> n >> m >> p;
init();
long long ans = 0;
for(int i = 1;i <= n;i ++) {
ans = (ans + c[n][i] * ksm(sum[i] , m-1) % p * ksm(2,(m-1) * (n-i) % p)) % p;
}
cout << ans % p << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
C. Sum of Suffix Sums
题意： 维护一个初始为空的数组的后缀和的和，有 q （q <= 5e5）次操作，每次操作：
· 给出两个整数 t 和 v ，将数组末尾开始到倒数第 t 位清空，然后在数组末尾接一个 v（0 <= t <= 数组长 ， 0 <= v <= 1e9）
输出每次操作后的后缀和的和。
注意： 结果可能很大，输出答案模 1e9 + 7 后的结果
样例：
case1:
输入：
5
0 1
0 2
1 3
0 6
2 100000
输出：
1
5
7
25
200001
case2:
输入：
1
0 1000000000
输出：
1000000000
分析： 这里维护后缀和的和，每次操作会将末尾 t 位元素清除，我们最后得到此时的后缀和的和是前 len - t 位的后缀和的和 + 上添加的 v 贡献的值，末尾添加一个 v 对答案的贡献为 (len - t + 1)v（此时后缀和共有新的数组长个即len - t + 1）, 然后更新数组长len即可。
对于如何得到第 len - t 位的后缀和的和有两种方法：
· 第 len - t 位后缀和的和一定是前面求过了的答案，用一个数组存下即可
· 第 len - t 位后缀和的和可由 第len 位的后缀和的和减去，第 len - t + 1 位到第 len 位元素的贡献值（即每一位元素到数组第一位的距离 * 元素值的类加），由于数组每次只添加一个元素，直接遍历复杂度样很低，故遍历累加即可
代码：
#include<bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int N = 5e5 + 5;
long long a[N] , ed , len , ans;
void solve() {
int q;cin >> q;
while(q --) {
int t , v;
cin >> t >> v;
int idx = len - t;
for(int i = idx + 1;i <= len;i ++) {
ans -= i * a[i] % p;
ans = (ans + p) % p;
}
len = idx + 1;
ans += len * (a[len] = v) % p;
ans %= p;
cout << (ans + p) % p << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}
H. World Finals
题意： 46th 、47th World Finals 同时举行，现给出 n 支队伍对 46th wf 的预测成绩，每支队伍给出一个字符串 s 与两个整数 p , t ， s 为队名，p为预测解题数，t为预测罚时，再同样给出 m 支队对 47th wf 的预测 ， 可能有某支队伍对两届比赛都进行了预测，但每支队伍只能打一场比赛。现 “lzr020506” 队对两场比赛都进行了预测，若比赛成绩和预测成绩一样，求“lzr020506”队可能最好的成绩是多少名次。
注意： 同一场比赛不会有解题数与罚时都一样的队伍。
样例：
case1:
输入；
5
pku 10 1513
thu 8 1195
lzr010506 8 1234
MIT 9 816
ntu 8 1325
4
mipt 9 1143
ntu 7 962
lzr010506 9 1523
pku 9 1068
输出：
2
分析： 直接贪心将除“lzr02005006”的对两场比赛都进行预测的队伍放到一场比赛，看另一场比赛的“lzr0020506”的名词取min即可。
操作用map判是否参加两场比赛，自写排序函数进行排序即可，
代码：
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<string,pair<int,int>> x , pair<string,pair<int,int>> y) {
if(x.second.first == y.second.first)
return x.second.second < y.second.second;
return x.second.first > y.second.first;
}
string T = "lzr010506";
void solve() {
int n;cin >> n;
map<string,pair<int,int>> f1 , f2;
for(int i = 1;i <= n;i ++) {
string s;int p , t;
cin >> s >> p >> t;
f1[s] = pair<int,int>(p,t);
}
int m;cin >> m;
for(int i = 1;i <= m;i ++) {
string s;int p , t;
cin >> s >> p >> t;
f2[s] = pair<int,int>(p,t);
}
vector<pair<string,pair<int,int>>> v1 , v2;
for(auto u : f1) {
if(f2.count(u.first) && u.first != T) continue;
v1.push_back(u);
}
for(auto u : f2) {
if(f1.count(u.first) && u.first != T) continue;
v2.push_back(u);
}
sort(v1.begin() , v1.end() , cmp);
sort(v2.begin() , v2.end() , cmp);
int ans = 1e9;
for(int i = 0;i < v1.size();i ++) {
if(v1[i].first == T) {ans = min(ans , i);break;}
}
for(int i = 0;i < v2.size();i ++) {
if(v2[i].first == T) {ans = min(ans , i);break;}
}
cout << ans + 1 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while(t --)
solve();
return 0;
}