A - BBP Formula
先将原式拆成四个级数，第一个级数为 \sum_1=\sum_{k=0}^\infty\frac{1}{16^k}\cdot\frac{1}{8k+1}，其余三个同理，分别计算每个级数的答案，则最终 \pi=4\sum_1-2\sum_2-\sum_3-\sum_4。将 \sum_1 乘上 16^{n-1}，即 \sum_{k=0}^\infty 16^{n-1-k}\cdot\frac{1}{8k+1}，则乘完之后的第一位小数即为原来的第 n 位。由于我们只需要保留小数部分，所以将级数拆为两部分：\sum_1=\sum_{k=0}^{n-1} 16^{n-1-k}\cdot\frac{1}{8k+1}+\sum_{k=n}^\infty 16^{n-1-k}\cdot\frac{1}{8k+1}，显然只有前半部分能对整数部分产生贡献，所以将前半部分的 16^{n-1-k}\bmod 8k+1 即可，用快速幂实现。最终就是先 O(n) 算出前半部分，由于后半部分的值非常小，算上20位就足够了，这样就算出了 \sum_1 将小数点右移 n-1 位后小数部分的结果，\sum_{2\dots4} 同理，最终将四个级数乘系数相加，取第一位小数即可。
B - Bridge
咕
C - Empty Convex Polygons
咕
D - Defense of the Ancients
咕
E - Five-round Show Hand
咕
F - Heron and His Triangle
由海伦公式可得三角形面积 S=\frac{t\sqrt{3(t^2-4)}}{4}。当 t=2k+1 时，易证 S 不可能为整数；当 t=2k 时，S=k\sqrt{3(k^2-1)}，则 3(k^2-1) 应为完全平方数 3\cdot 3T^2，可得 k^2-3T^2=1，为一个佩尔方程（Pell's equation），其最小解为 x_1=2,y_1=1，由佩尔方程解的递推式 x_{i+1}=x_1x_i+ny_1y_i,y_{i+1}=x_1y_i+y_1x_i，可得其所有解，且解的增长速度为指数级别。所以利用递推式找到 t=2k 恰好大于等于 n 的解即可。总复杂度 O(\log n)。
G - Infinite Fraction Path
当一条路径的长度大于等于 n 时，一定已经包含了循环节。所以问题就转换成了，有 n 个长度为 n 的字符串，让你找出字典序最大的那个，类似后缀数组倍增即可，总复杂度 O(n\log n)。具体实现的时候，先 O(n\log n) 预处理出 \mathrm{next}[i][j]，表示从 i 开始跳 2^j 步会跳到哪里；然后这里的后缀数组与一般字符串处理中后缀数组的不同在于，在计算tsa时，不能通过后半段字符串的sa直接求出，因为本题中字符串不是线性的，而是以基环内向树森林的形式构成的，可能存在多个前半段与同一个后半段对应，所以用基数排序第一步求出tsa即可。
H - Legends of the Three Kingdoms
咕
I - Little Boxes
签到题。注意当四个数均等于 2^{62} 时，和为 2^{64} 恰好会爆unsigned long long，特判一下就好。
J - New Self-describing Sequence
咕
K - Rabbits
注意到当左右两端其中某一端存在连续的两只兔子时，答案为此时所有兔子之间的空位数之和。所以当当左右两端均不存在连续的两只兔子时，左右两端哪边的空位少，就跳哪只兔子。所以答案就是总空位数减去左右两端空位数的最小值。
L - Tree
当某一条边两边的节点数都大于等于 k 时，这条边一定会被加入到答案中。所以dfs统计一下这样的边的个数就是答案。总复杂度 O(n)。
M - Wandering Robots
咕
Code
A - BBP Formula
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define int long long
using namespace std;
int T, n;
int fpow(int x, int k, int p) {
int ans = 1;
while (k) {
if (k & 1) {
ans = ans * x % p;
}
x = x * x % p, k >>= 1;
}
return ans;
}
char getc(int x) {
if (x < 10) {
return x + '0';
}
return x - 10 + 'A';
}
signed main() {
scanf("%lld", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%lld", &n);
double s1 = 0, s2 = 0, s3 = 0, s4 = 0;
for (int i = 0; i < n; i++) {
s1 += (double)fpow(16, n - 1 - i, 8 * i + 1) / (8 * i + 1);
s2 += (double)fpow(16, n - 1 - i, 8 * i + 4) / (8 * i + 4);
s3 += (double)fpow(16, n - 1 - i, 8 * i + 5) / (8 * i + 5);
s4 += (double)fpow(16, n - 1 - i, 8 * i + 6) / (8 * i + 6);
}
for (int i = n; i <= n + 20; i++) {
s1 += pow(16, n - 1 - i) / (8 * i + 1);
s2 += pow(16, n - 1 - i) / (8 * i + 4);
s3 += pow(16, n - 1 - i) / (8 * i + 5);
s4 += pow(16, n - 1 - i) / (8 * i + 6);
}
double res = 4 * s1 - 2 * s2 - s3 - s4;
int ans = ((int)floor(res * 16) % 16 + 16) % 16;
printf("Case #%lld: %lld %c\n", cas, n, getc(ans));
}
}
B - Bridge
C - Empty Convex Polygons
D - Defense of the Ancients
E - Five-round Show Hand
F - Heron and His Triangle
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define int __int128_t
using namespace std;
int T, n;
istream& operator>>(istream& in, __int128_t& x) {
string s;
in >> s;
x = 0;
for (int i = 0; i < s.size(); i++) {
x = x * 10 + s[i] - '0';
}
return in;
}
ostream& operator<<(ostream& out, __int128_t x) {
if (x == 0) {
out << "0";
return out;
}
stack<signed> st;
while (x) {
st.push(x % 10), x /= 10;
}
while (!st.empty()) {
out << st.top();
st.pop();
}
return out;
}
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
int x = 2, y = 1;
while (x * 2 < n) {
int nx = 2 * x + 3 * y;
int ny = 2 * y + x;
x = nx, y = ny;
}
cout << x * 2 << endl;
}
}
G - Infinite Fraction Path
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 150005
#define MAX_L 20
#define sqr(x) ((long long)(x) * (x))
using namespace std;
int T, n;
int cnt[MAX_N];
int sa[MAX_N], tsa[MAX_N];
int rk[MAX_N], trk[MAX_N];
int nxt[MAX_N][MAX_L];
char d[MAX_N];
int mov(int x) {
return (sqr(x) + 1) % n;
}
void getnxt() {
for (int i = 0; i < n; i++) {
nxt[i][0] = mov(i);
}
for (int j = 1; j < MAX_L; j++) {
for (int i = 0; i < n; i++) {
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
}
}
void suffix() {
int mx = max(n, 10);
for (int i = 0; i < mx; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[rk[i] = d[i]]++;
for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
for (int j = 0; (1 << j) < n; j++) {
for (int i = 0; i < mx; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[rk[nxt[i][j]]]++;
for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) tsa[--cnt[rk[nxt[i][j]]]] = i;
for (int i = 0; i < mx; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[rk[i]]++;
for (int i = 1; i < mx; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tsa[i]]]] = tsa[i];
for (int i = 0; i < n; i++) trk[i] = rk[i];
int tot = 0;
rk[sa[0]] = tot;
for (int i = 1; i < n; i++) {
if (trk[sa[i]] != trk[sa[i - 1]] ||
(trk[sa[i]] == trk[sa[i - 1]] && trk[nxt[sa[i]][j]] != trk[nxt[sa[i - 1]][j]])) {
rk[sa[i]] = ++tot;
} else {
rk[sa[i]] = tot;
}
}
if (tot == n - 1) {
break;
}
}
}
int main() {
scanf("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%d%s", &n, d);
for (int i = 0; i < n; i++) {
d[i] = 9 - (d[i] - '0');
}
getnxt();
suffix();
printf("Case #%d: ", cas);
for (int i = 1, t = sa[0]; i <= n; i++, t = mov(t)) {
printf("%d", (int)(9 - d[t]));
}
printf("\n");
}
}
H - Legends of the Three Kingdoms
I - Little Boxes
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MX (1ULL << 62)
#define int unsigned long long
using namespace std;
int T, a, b, c, d;
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> a >> b >> c >> d;
if (a == MX && b == MX && c == MX && d == MX) {
cout << "18446744073709551616" << endl;
} else {
cout << a + b + c + d << endl;
}
}
}
J - New Self-describing Sequence
K - Rabbits
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 505
using namespace std;
int T, n;
int a[MAX_N];
int sp[MAX_N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
int sum = 0;
for (int i = 1; i < n; i++) {
sp[i] = a[i + 1] - a[i] - 1;
sum += sp[i];
}
printf("%d\n", sum - min(sp[1], sp[n - 1]));
}
}
L - Tree
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 200005
using namespace std;
int T, n, K, ans;
int siz[MAX_N];
vector<int> e[MAX_N];
void dfs(int x, int p) {
siz[x] = 1;
for (int i = 0; i < e[x].size(); i++) {
int t = e[x][i];
if (t != p) {
dfs(t, x);
siz[x] += siz[t];
if (siz[t] >= K && n - siz[t] >= K) {
ans++;
}
}
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; i++) {
e[i].clear();
}
int x, y;
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
e[x].push_back(y);
e[y].push_back(x);
}
ans = 0;
dfs(1, 0);
printf("%d\n", ans);
}
}
M - Wandering Robots