【2022.12.30提高组模拟】依依寺（yiyi）
Problem Description
从前有个寺庙，名为依依寺。寺庙因《诗经.小雅》中的“昔我往矣，杨柳依依。
今我来思，雨雪霏霏。“而得名。
庙里有个老和尚和小和尚。老和尚叫章丘样，小和尚叫章扬扬。老和尚说“从前有个寺庙，名为依依寺。庙里有个老和尚和小和尚。老和尚叫章丘样，小和尚叫章扬扬……”
有一天，老何尚在拨算盘。他脑海中蹦出了这么一道题：
有n = a + b + c个数，其中有a个0，b个1，c 个2。我章丘样和你章扬扬轮流取数，我先手。设累计取出来的数总和为 s，若s 是3的倍数，那么这一方输。如果数字取完了游戏还没结束，则没有数可以取的这一方输。
由于a, b, c 可能很大，两和尚无法手玩得到，所以想让你编程来帮帮他们。Input
第一行，输入数据组数T，表示有T 局游戏。
接下来T行，每行输入a, b, c表示老和尚和小和尚的一局游戏。Output
输出共 T 行，若老和尚（即先手）赢，输出 First，否则输出 Second。
Sample Input Copy
3 0 0 0 1 0 0 1 1 1Sample Output Copy
Second Second Second 【样例 说明】 对于a = 0, b = 0, c = 0，先手无法操作，所以先手输； 对于a = 1, b = 0, c = 0，先手只能取0 ，但是这样s = 0为3的倍数，所以先手输； 对于a = 1, b = 1, c = 1 ，若先手取1，则后手取0，先手只能取2 ；若先手取 2， 则后手取0，先手也只能取1。因此先手怎样都输。Data Constraint
对于所有数据，数据组数均满足 1 ≤ T ≤ 10^5。
对于 30% 的数据，1 ≤ a, b, c ≤ 10；
对于 60% 的数据，1 ≤ a, b, c ≤ 100；
对于 80% 的数据，1 ≤ a, b, c ≤ 10^9；
对于 100% 的数据，1 ≤ a, b, c ≤ 10^18。
除去0，发现取的顺序一定是1，1，2，1，2……或2，2，1，2，1……比谁的多
0的作用是逆转先后手顺序，只在乎奇偶性。
然后代码就出来了：
#include <cstdio>
#define ll long long
ll T, a, b, c;
int main() {
freopen("yiyi.in", "r", stdin);
freopen("yiyi.out", "w", stdout);
scanf("%lld", &T);
while(T--) {
scanf("%lld %lld %lld", &a, &b, &c);
a %= 2;
// 先取2b
// 1:1:2:1:2:1:2:1:2:1
if(b >= 2) {
if(b-2 < c) {
if(!a) {
printf("First\n");
continue;
}
} else {
if(a) {
printf("First\n");
continue;
}
}
} else if(b == 1) {
if(!a) {
printf("First\n");
continue;
}
}
// 先取2c
// 2:2:1:2:1:2:1:2:1
if(c >= 2) {
if(c-2 < b) {
if(!a) {
printf("First\n");
continue;
}
} else {
if(a) {
printf("First\n");
continue;
}
}
} else if(c == 1) {
if(!a) {
printf("First\n");
continue;
}
}
printf("Second\n");
}
}
【2022.12.30提高组模拟】武义寺(wuyi)
Problem Description
从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给，小和尚叫扶弱呱。老和尚说“从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。
老和尚叫扶弱给，小和尚叫扶弱呱……”
有一天，扶弱给在潜心研究排列。他在脑中随机一个排列的时候，脑海里冒出了
这样一个问题：
对于一个排列p = {1,2, . . . , n} ，记val(p)等于最小的i 满足i > ai，如不存在则
val(p) = n + 1。
可是val(p)的期望值是多少呢？显然，扶弱给没学过编程，需要你来帮帮他。Input
输入一个数n。
Output
输出val(p)的期望值，答案对998244353取模。
Sample Input Copy
2Sample Output Copy
499122179 【样例 1 说明】 对于排列p = [1,2]，val(p) = 3；对于排列p = [2,1]，val(p) = 2。因此期望值为5/2 。Data Constraint
对于 30% 的数据，1 ≤ n ≤ 5 ；
对于 50% 的数据，1 ≤ n ≤ 20 ；
对于 80% 的数据，1 ≤ n ≤ 10^5 ；
对于 100% 的数据，1 ≤ n ≤ 10^6。
枚举 \(\text{val}(p)=i\)，说明 \(1\sim (i-1)\) 都有 \(a_i\ge i\)，第 \(i\) 位有 \(i > a_i\)，后面随便排。
首先化简题目，设 \(n=6,k=4\)，第一位能选1到n，第二位能选2到n，第三位能选3到n……第k位能选k到n。
先考虑约束大的第k位，有 \(n-k+1\) 种选择，选择一种后发现第k-1位方案也少了一种，所以也是 \(n-k+1\) 种选择，最终有 \((n-k+1)^k\)。
枚举第 \(a_i=j\)，然后有 \(1\sim j\) 为的方案数都减一，\((j+1)\sim (i-1)\) 不变。
\[\sum_{j=1}^{i-1} (n-i+2)^{i-j-1}\times(n-i+1)^j \]考虑化简，设 \(a=n-i+1\)，有：
\[\begin{aligned} \sum_{j=1}^{i-1} (a+1)^{i-j-1}\times a^j &= \sum_{j=1}^{i-1} (a+1)^{i-1}\times(a+1)^{-j}\times a^j \\ &= (a+1)^{i-1}\times\sum_{j=1}^{i-1} (\frac{a}{a+1})^j \\ & \text{设}u=\frac{a}{a+1}\\ &= (a+1)^{i-1}\times\sum_{j=1}^{i-1} u^j \\ &= (a+1)^{i-1}\times \frac{u^{i}-u}{u-1} \\ &= (a+1)^{i-1}\times \frac{(\frac{a}{a+1})^{i}-\frac{a}{a+1}}{\frac{a}{a+1}-1}\\ &= (a+1)^{i-1}\times \frac{(\frac{a}{a+1})^{i}-\frac{a}{a+1}}{\frac{a}{a+1}-\frac{a+1}{a+1}}\\ &= (a+1)^{i-1}\times \frac{(\frac{a}{a+1})^{i}-\frac{a}{a+1}}{\frac{-1}{a+1}}\\ &= (a+1)^{i-1}\times ((\frac{a}{a+1})^{i}-\frac{a}{a+1})\times\frac{a+1}{-1}\\ &= (a+1)^{i-1}\times (\frac{a^{i}}{(a+1)^{i}}-\frac{a(a+1)^{i-1}}{(a+1)^{i}})\times\frac{a+1}{-1}\\ &= (a+1)^{i-1}\times (\frac{a^{i}-a(a+1)^{i-1}}{(a+1)^{i}})\times\frac{a+1}{-1}\\ &= (a+1)^{i}\times (\frac{a^{i}-a(a+1)^{i-1}}{(a+1)^{i}})\times(-1)\\ &= (a^{i}-a(a+1)^{i-1})\times(-1)\\ &= a(a+1)^{i-1}-a^{i}\\ \end{aligned} \]然后有后面的 \(i+1\) 到 \(n\)，全排列即可。
代码：
#include <cstdio>
#define P 998244353
#define ll long long
#define N 1000010
ll n;
ll invn;
ll fact[N];
ll b[N];
ll ans;
ll qpow(ll x, ll y) {
if(y == 0) return 1;
if(y % 2 == 1) return x * qpow(x, y-1) % P;
ll tmp = qpow(x, y/2);
return tmp * tmp % P;
}
inline ll fun(ll x) {
return (x%P+P)%P;
}
int main() {
freopen("wuyi.in", "r", stdin);
freopen("wuyi.out", "w", stdout);
scanf("%lld", &n);
fact[0] = 1;
for(ll i = 1; i <= n; i++) (fact[i] = fact[i-1] * i) %= P;
for(ll i = 1; i <= n; i++) {
ll a = n-i+1;
(ans += fun(a * qpow(a+1, i-1) % P - qpow(a, i)) * fact[n-i] % P * i) %= P;
}
// 易得val(p)=n+1只有一种情况
(ans += n+1) %= P;
// 总共有n!种情况，求期望
(ans *= qpow(fact[n], P-2)) %= P;
printf("%lld", ans);
}