邮寄
开场直接看 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;
}
标签:5.0,tmp,return,pbs,int,long,fib
From: https://www.cnblogs.com/leavenothingafterblog/p/18426978/speedrun_v5-0