邮寄
开场直接看 A。A 做不出来。
浏览了一下，发现 A 是 sb 题，直接做了。
BCD 全都不会做。
推了好久的 B，想出来了，然后写过了。
CD 一个暴力，一个乱搞，然后撤退。
A 依依寺
\(a\) 没用，对 \(b\) 和 \(c\) 分类讨论。
死于不开 long long 见祖宗。
#include <bits/stdc++.h>
using namespace std;int t, a, b, c, ans;int main() {//freopen("yiyi.in", "r", stdin);//freopen("yiyi.out", "w", stdout);for(cin >> t; t--; ) {cin >> a >> b >> c;ans = 0;if((!b) && (!c)) {cout << "Second" << '\n';continue;}if(b) {b--;ans |= (b <= c) ^ (a & 1);b++;}if(c) {c--;ans |= (c <= b) ^ (a & 1);c++;}cout << (ans? "First" : "Second") << '\n';}return 0;
}
B 武义寺
考虑每一个 \(\operatorname{val}\) 的可能取值。
对于取值为 \(i\) 的情况，前 \(i - 1\) 个数必须满足 \(j \leq a_j\)，第 \(i\) 个数必须满足 \(i > a_i\)，其他随便。
先考虑第一个条件。
记 \(pbs_i\) 表示 前 \(i\) 个数满足 \(j \leq a_j\) 的概率，从后往前看，易得 \(pbs_i = \frac{(n - i + 1)^i \times (n - i)!}{n!}\)。
然后考虑第二个条件。可知 \(\operatorname{val}(p) = i\) 的概率是 \(pbs_{i - 1} - pbs_i\)。
然后就可以直接做了。
#include <bits/stdc++.h>
#define int long long
using namespace std;const int kMod = 998244353;int n, fac[1000010], ivs[1000010], inv[1000010], pbs[1000010], prb[1000010], ans;int qpow(int x, int y) {int rs = 1;for(; y; y >>= 1) {if(y & 1) {rs = rs * x % kMod;}x = x * x % kMod;}return rs;
}int qinv(int x) {return qpow(x, kMod - 2);
}void init() {fac[0] = 1;for(int i = 1; i <= 1000000; i++) {fac[i] = fac[i - 1] * i % kMod;}ivs[1000000] = qinv(fac[1000000]);for(int i = 999999; i >= 0; i--) {ivs[i] = ivs[i + 1] * (i + 1) % kMod;}for(int i = 1; i <= 1000000; i++) {inv[i] = ivs[i] * fac[i - 1] % kMod;}
}signed main() {//freopen("wuyi.in", "r", stdin);//freopen("wuyi.out", "w", stdout);init();cin >> n;pbs[0] = 1;for(int i = 1; i <= n; i++) {pbs[i] = qpow(n - i + 1, i) * fac[n - i] % kMod * ivs[n] % kMod;}for(int i = 1; i <= n + 1; i++) {prb[i] = (pbs[i - 1] - pbs[i] + kMod) % kMod;ans = (ans + i * prb[i]) % kMod;}cout << ans << '\n';return 0;
}
C 依久依久
超级大数学。
区间复杂东西的复杂运算，可差分，果断祭出前缀和。
对于 \(l = 1\)，不难想到一位一位处理。
找到 \(n\) 的最高位，设是第 \(k\) 位，对应的数是 \(fib_k\)。我们把这一位的贡献算上，然后递归处理。
写出来就是：
\[\operatorname{S}(n) = \operatorname{S}(fib_k - 1) \ \oplus \ \operatorname{S}(n - fib_k) \ \oplus \ \begin{cases} fib_k &\text{if } n - fib_k + 1 \text{ is odd} \\ 0 &\text{otherwise} \end{cases}
\]
// 实际写出来的代码短得神奇
#include <bits/stdc++.h>
#define int long long
using namespace std;int t, l, r, ans, f[114], n;
map<int, int> mem;int cal(int x) {if(!x) {return 0;}if(mem.find(x) != mem.end()) {return mem[x];}int tmp = upper_bound(f + 1, f + n + 1, x) - f - 1;return mem[x] = (cal(f[tmp] - 1) ^ cal(x - f[tmp]) ^ (((x - f[tmp] + 1) & 1) * f[tmp]));
}signed main() {freopen("yijiu.in", "r", stdin);freopen("yijiu.out", "w", stdout);f[0] = f[1] = 1;for(n = 2; (f[n] = f[n - 1] + f[n - 2]) <= (int)(1e18); n++) {}for(cin >> t; t--; ) {cin >> l >> r;cout << (cal(r) ^ cal(l - 1)) << '\n';}return 0;
}
