A. 循环与非
题目描述
给定长度为 \(n\) 的序列 {\(a_n\)}，每一个数字都不超过 \(2\) 的 \(k\) 次方。给定 \(m\) 次操作，每次操作形如：
0 x y ：将 \(a[x]\) 改为 \(y\)。
1 x y ：令 \(t=y\) NAND \(a[0]\) NAND \(a[1]\) NAND \(a[2]\) NAND ... NAND \(a[i\) \(mod\) \(n]\) NAND ... NAND \(a[(x*n-1)\) \(mod\) \(n]\)。
NAND 代表按位与非操作。
求所有计算结果的 \(t\) 的异或和。
输入格式
第一行包含三个正整数 \(n，m，k\)。
接下来一行 \(n\) 个整数 \(a_0 \sim a_{n-1}\)。
接下来 \(m\) 行每行三个整数 \(op，x，y\)。
输出格式
输出一行一个整数表示答案。
样例输入
2 3 3
1 2
1 2 3
0 0 3
1 2 2
样例输出
2
样例输入
7 4 4
4 6 4 7 10 9 11
1 5 7
1 7 14
0 6 7
1 6 5
样例输出
9
数据规模
\(1 \le n,m \le 10^4\)，\(0 \le y < 2^k\)
操作 \(0\) 中，\(0 \le x < n\)
操作 \(1\) 中，\(1 \le x < 10^9\)
\(1 \le k \le 30\)
点击查看代码
#include<iostream>
#include<set>
using namespace std;
int m, n, k, a[10005];
set<int> st[30];
int find(int i) { return st[i].empty() ? -1 : *st[i].rbegin(); }
int main() {
cin >> n >> m >> k;
int tmp;
for(int i = 0; i < n; i ++) {
cin >> tmp;
for(int j = 0; j < k; j ++)
if(!(tmp & 1 << j)) st[j].insert(i);
}
int opt, x, y, res, t = 0, last;
while(m --) {
cin >> opt >> x >> y;
if(opt == 0)
for(int i = 0; i < k; i ++)
if(!(y & 1 << i)) st[i].insert(x);
else st[i].erase(x);
else {
res = 0;
for(int i = 0; i < k; i ++){
last = find(i);
if(last == -1) res += (1ll * x * n + (y >> i & 1) & 1) << i;
else res += (n - last & 1) << i;
}
t ^= res;
}
}
cout << t;
return 0;
}
编译结果
compiled successfully
time: 100ms, memory: 7232kb, score: 100, status: Accepted
> test 1: time: 1ms, memory: 3408kb, points: 10, status: Accepted
> test 2: time: 5ms, memory: 3448kb, points: 10, status: Accepted
> test 3: time: 25ms, memory: 7232kb, points: 10, status: Accepted
> test 4: time: 3ms, memory: 4076kb, points: 10, status: Accepted
> test 5: time: 17ms, memory: 5248kb, points: 10, status: Accepted
> test 6: time: 2ms, memory: 3544kb, points: 10, status: Accepted
> test 7: time: 10ms, memory: 3720kb, points: 10, status: Accepted
> test 8: time: 10ms, memory: 3604kb, points: 10, status: Accepted
> test 9: time: 18ms, memory: 4716kb, points: 10, status: Accepted
> test 10: time: 9ms, memory: 3476kb, points: 10, status: Accepted
B. 蹦蹦萝卜
题目描述
有一个环状的操场，操场被分割为 \(n\) 个小块，每个小块上写着一个数字。
有一只小白兔站在操场的起点 \(1\)，它每次可以跳 \(k\) 个小块，然后拿走等同于它跳之前所站小块上数字数量的胡萝卜，问它跳 \(m\) 次，总共可以拿到几个胡萝卜？
小白兔在 \(i\) 处时，它跳到的下一个位置是 \((i+k)\) \(mod\) \(n + 1\)。
如果能够算出来的话，小白兔就能把所有的胡萝卜都带回家吃啦！
答案对 \(10^9+7\) 取模。
输入格式
第一行包含两个正整数 \(n\) 和 \(k\)，
第二行 \(n\) 个正整数 \(a_1...a_n\) 每个小块上的数字，
第三行一个正整数 \(m\)。
输出格式
输出一行一个整数表示答案。
样例输入
5 1
1 10 100 1000 10000
3
样例输出
10101
数据规模
\(1 \le k \le n \le 10^6\)，\(1 \le a_i \le 10^6\), \(1 \le m \le 10^{18}\)
点击查看代码
#include<iostream>
#include<set>
using namespace std;
#define MOD 1000000007
int n, k, a[1000005], p[1000005][70], c[1000005][70];
long long m;
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];
cin >> m;
for(int i = 1; i <= n; i ++) {
p[i][0] = (i + k) % n + 1;
c[i][0] = a[i];
}
for(int j = 1; j <= 60; j ++) {
for(int i = 1; i <= n; i ++) {
p[i][j] = p[p[i][j - 1]][j - 1];
c[i][j] = (c[i][j - 1] + c[p[i][j - 1]][j - 1]) % MOD;
}
}
long long res = 0;
int x = 1;
for(int j = 0; j < 63; j ++) {
if(m & 1LL << j) {
res += c[x][j];
x = p[x][j];
}
}
cout << res % MOD << endl;
return 0;
}
编译结果
compiled successfully
time: 12253ms, memory: 496952kb, score: 100, status: Accepted
> test 1: time: 1775ms, memory: 386052kb, points: 10, status: Accepted
> test 2: time: 106ms, memory: 58732kb, points: 10, status: Accepted
> test 3: time: 1147ms, memory: 262252kb, points: 10, status: Accepted
> test 4: time: 324ms, memory: 116136kb, points: 10, status: Accepted
> test 5: time: 1937ms, memory: 410032kb, points: 10, status: Accepted
> test 6: time: 273ms, memory: 99752kb, points: 10, status: Accepted
> test 7: time: 2433ms, memory: 496952kb, points: 10, status: Accepted
> test 8: time: 1629ms, memory: 360016kb, points: 10, status: Accepted
> test 9: time: 1412ms, memory: 313324kb, points: 10, status: Accepted
> test 10: time: 1217ms, memory: 275484kb, points: 10, status: Accepted
C. 超大范围幂运算
时间：1s 空间：256M
题目描述
有 \(3\) 个整数 \(a, b, c\)，求 \(a^b\) \(mod\) \(c\)
输入格式
第一行包含一个整数 \(T\)，表示测试数据组数。
对于每组测试数据，包含 \(3\) 个整数 \(a, b, c\)。
输出格式
对于每组测试数据，输出一个整数表示答案。
样例1输入
6
0 0 1
0 0 100
2 5 17
0 10 100
100 0 1000000000000000000
114 514 1919810
样例1输出
0
1
15
0
1
290606
约定与提示
对于 \(100\%\) 的数据，\(1 \le T \le 5000\)，\(0 \le a,b \le 10^{18}\); \(1 \le c \le 10^{18}\)
点击查看代码
#include<iostream>
#include<set>
using namespace std;
long long T, a, b, c;
long long qadd(long long a, long long b, long long p) {
long long res = 0;
while(b) {
if(b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
long long quickpow(long long x, long long n, long long m){
if(n == 0) return 1 % m;
long long res = quickpow(qadd(x, x, m), n / 2, m);
if(n & 1) res = qadd(res, x, m);
return res;
}
int main() {
cin >> T;
while(T --) {
cin >> a >> b >> c;
printf("%lld\n", quickpow(a, b, c));
}
return 0;
}
编译结果
compiled successfully
time: 597ms, memory: 3524kb, score: 100, status: Accepted
> test 1: time: 1ms, memory: 3424kb, points: 0, status: Accepted
> test 2: time: 1ms, memory: 3524kb, points: 20, status: Accepted
> test 3: time: 1ms, memory: 3492kb, points: 20, status: Accepted
> test 4: time: 50ms, memory: 3484kb, points: 20, status: Accepted
> test 5: time: 67ms, memory: 3476kb, points: 20, status: Accepted
> test 6: time: 477ms, memory: 3496kb, points: 20, status: Accepted