前言
我的codeforces账号：keguaiguai
求关注、求关注、求关注
基本情况
济南站情况大致是：
1题快：铜牌
2题快：银牌
4题整：金牌
8题快：出线
我们队伍第一次参加区域赛，由于做题时紧张，又赶上期中考试和数学竞赛，于是爆零了。
难度分布
C、D、J、K四题是竞赛中过题队伍数在100支以上的，但是在本次竞赛中一共做出4题的只有35支队伍。
K-签到题
C-铜牌题
J-银牌题
D-银牌题
其余9题为金牌题。因难度过高，网上题解也很少，故只能提供铜银题的题解。
K 寻找椎名真冬
命题人
jiangly
题目背景
Mafuyu：全名Shiina Mafuyu，即椎名真冬，日本动画《学生会的一己之见》的女主角之一。
Kanade：全名Tachibana Kanade，即立华奏，日本动画《Angle Beats!》及衍生作品中人物。
Sekai：“Sekai”是一个“源于想象力“的世界，取材于近代日本的涩谷，初音未来等歌手将出现在这里，是《世界计划 彩色舞台》中的世界。游戏英文名称Project Sekai，是SEGA GAMES与Colorful Palette合作开发的一款初音企划手游。
题目翻译
椎名真冬藏在了世界里，立华奏正在寻找她。
这个世界，只有许多房间。世界里有n间房，编号1到n。另外，n-1对房间直接由通道连接，这样就可以通过使用一个或多个通道，从一间房移动到其它任意一间。也就是说，世界里的房间形成了一棵树。
立华奏在1号房间，她知道椎名真冬也许等可能地藏在除了1号房间的其它任意一个房间。每一秒钟，立华奏能移动到与她目前所在房间相邻的房间。只要立华奏和椎名真冬处于同一间房，立华奏马上就能找到椎名真冬。如果立华奏采取最佳策略，那么立华奏找到椎名真冬的最短期望时间是多少？
思路
本题求的是期望用时。这是一个非透明信息静态博弈，通过分析样例可以发现，无论立华奏采取何种策略从1号根节点开始遍历这棵树，求得的最短期望时间都相同。因此先用vector建立无向图存储树形结构，然后以一号结点为根结点开始用dfs递归遍历整棵树。注意在进栈和出栈时，根据深度递归的特性，令当前时间加1，模拟走过某个结点和离开某个结点时，时间流动的过程。每先进入一个结点，就令总时间加上当前的时间。最后让时间总和除以n-1，就得到n-1个结点的平均期望时间。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
vector<int> son[maxn];
int ans, tim;
void dfs(int cur, int fa) {
tim++;
for (int i = 0; i < son[cur].size(); i++) {
if (son[cur][i] != fa) {
ans += tim;
dfs(son[cur][i], cur);
}
}
tim++;
}
int main()
{
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a, b;
for (int i = 1; i <= n; i++)son[i].clear();
for (int i = 1; i < n; i++) {
cin >> a >> b;
son[a].push_back(b);
son[b].push_back(a);
}
ans = 0, tim = 0;
dfs(1, 0);
double x = ans*1.0 / (n - 1);
printf("%.10lf\n", x);
}
return 0;
}
感想
第一次参加区域赛爆零了，当时做这题不知道为什么，考场上调了几个小时都没调出来，寒假有时间了现在自己再做一遍，发现这题非常简单，想了一会，直接写代码就AC了。不知道考试时中了什么魔咒，能紧张成那个样子。记得当时应该是思路想偏了，一开始就是按照这种思路写的代码，只是交了没过，就没有再去修改代码，而是换了其他思路写这个题，三个人越写心态越崩，就炸掉了。我记得当时dfs写得非常复杂，绝对是没有利用栈的特性，而是在那里瞎写。
这次比赛，获得铜牌的条件是这道题在半小时之内做出来。只需要快速做出这一道题，就可以拿铜牌。现在我后悔也来不及了，安心准备昆明站吧。
J 行列式
题目背景
Alice：爱丽丝·玛格特洛伊德，系列作品《东方project》中的角色。
题目翻译
爱丽丝想利用矩阵
A
T
A
A^{T}A
ATA的优良性质求矩阵
A
T
A
A^{T}A
ATA的行列式。将A的行列式记为det(A)，满足det(
A
T
A
A^{T}A
ATA)=
d
e
t
(
A
)
2
det(A)^{2}
det(A)2。爱丽丝利用这个性质求绝对值|det(A)|。但不幸的是，当|det(A)|≠0，这个方法无法得出det(A)是正的还是负的。
已知矩阵A和det(A)的绝对值，判断A是正的还是负的。
数据大小：|det(A)|的绝对值不超过10000位，矩阵中每个元素不超过
1
0
9
10^{9}
109。
思路
由于|det(A)|的绝对值过于巨大，不可能直接通过高斯消元求出det(A)。只能考虑用某种手段降低数据大小，由此可以想到取模。|det(A)|的绝对值已知，但它是个大数，可以利用大数取模模板对det(A)的绝对值取模，再利用高斯消元在取模意义下求det(A)取模后的值。正数和负数取模后得到的值不同，但需满足一定条件。推导如下：
推导
设有正整数x， x m o d p = = q xmodp==q xmodp==q，则q<p， x = k p + q x=kp+q x=kp+q。故 ? x m o d p = = ( ? k p ? q ) m o d p = = ( ? k p ? q + k p + p ) m o d p = = ( p ? q ) m o d p = = p ? q -x mod p ==(-kp-q) mod p==(-kp-q+kp+p)modp==(p-q)modp==p-q ?xmodp==(?kp?q)modp==(?kp?q+kp+p)modp==(p?q)modp==p?q。若 x m o d p ≠ ? x m o d p xmodp≠-xmodp xmodp?=?xmodp，需满足q≠p-q，即p≠2q。因此当p为奇数时，p不为2的倍数，满足正数和负数取模后得到的值不同。
大数取模
如何对大数取模？以1234为例，将大整数分解成这种形式： 1234 = ( ( 1 ? 10 + 2 ) ? 10 + 3 ) ? 10 + 4 1234=((1*10+2)*10+3)*10+4 1234=((1?10+2)?10+3)?10+4，即从高位到低位，分别对大数的每一位上的数取模再乘10，再加上下一位上的数重复上述操作。
模意义下高斯消元
如何在高斯消元时取模？首先回顾高斯消元的原理。对于一个矩阵，可以先以第一行为参考，第二至n行分别减去第一行乘一个倍数，使得第二至n行的第一个元素恰好为0。再以第二行为参考，重复上述过程，直到化为行阶梯型矩阵。如果是解多元线性方程组，此时由这个矩阵的最后一行，直接得出最后一个未知量的值。然后代入，得到倒数第二行的倒数第二个未知量的值，以此类推，直到求出所有未知量的值。如果是求这个矩阵的行列式的值，直接将对角线上的所有元素相乘即可。对于取模，在算倍数时需要用除法，则利用费马小定理求模意义下的除法值。回顾一下费马小定理：
(
a
÷
b
)
m
o
d
(a÷b) mod
(a÷b)mod
p
=
=
(
a
?
i
n
v
(
b
)
)
m
o
d
p
p == (a * inv(b)) mod p
p==(a?inv(b))modp
其中（inv(b) ==
b
p
?
2
b^{p-2}
bp?2）mod p，且b与p互素
b
p
?
2
b^{p-2}
bp?2直接利用取模意义下的快速幂进行计算。由于b与p互素，且b小于
1
0
9
10^{9}
109，p是奇数。要满足这些条件，最好让p比b大，且p本身也取素数，那么b就不会成为p的因子。故采用较常见的1e9+7。
细节
注意高斯消元时，如果对角线上的值为0，则当前列无法消去，需要将含0的这一行与最后面不含0的一行交换，才能再继续消元。而且行列式中，一旦换行就会改变行列式值的正负，需要考虑在内。如果后面的行这一列全为0，那么行列式的值就为0，因为前面不为0的数都可以通过列消元消为0。由于有些元素为负值，取模时需格外注意加上模数。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 105;
const int mod = 1e9 + 7;
int a[maxn][maxn];
int cal(string x, int p) {
int sum = 0;
for (int i = 0; i < x.size(); i++) {
sum = (sum * 10 + (x[i] - '0')) % p;
}
return sum;
}
int quick_pow(int a, int b, int p) {
int ans = 1; a %= p;
while (b) {
if (b & 1)ans = ans*a%p;
a = a*a%p;
b = b >> 1;
}
return ans;
}
int get_inv(int x, int p) {
return quick_pow(x, p - 2, p);
}
int guass(int a[maxn][maxn], int n, int p) {
int res = 1;
for (int i = 1; i <= n; i++) {
if (a[i][i] == 0) {
bool flag = false;
for (int j = i + 1; j <= n; j++) {
if (a[j][i]) {
flag = true;
for (int k = i; k <= n; k++)swap(a[j][k], a[i][k]);
res = -res;
break;
}
}
if (flag == false)return 0;
}
res = (res*a[i][i] + p) % p;
for (int j = i + 1; j <= n; j++) {
int x = a[j][i] * get_inv(a[i][i], p) % p;
for (int k = i; k <= n; k++) {
a[j][k] = (a[j][k] - a[i][k] * x%p + p) % p;
}
}
}
return res;
}
signed main()
{
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
string s;
cin >> s;
int ans = cal(s, mod);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
int res = guass(a, n, mod);
if (res == ans)puts("+");
else puts("-");
}
return 0;
}
感想
考试之前做了去年济南站的题，还专门背了高斯消元的板子，结果考试的时候完全想不到对大数取模的操作。就算是想到了，也不一定能实现代码，毕竟这类题目平时练的太少。复盘的时候，发现这道题目居然卡常数，要关同步流才能过，运行时间965ms，过于危险。还要注意模数的选取必须满足费马小定理。总之，如果没有见过类似取模的题目，本题几乎很难做出来。
D 等差数列
题目背景
Alice：爱丽丝·玛格特洛伊德，身份是魔法使，居住在魔法森林-玛格特罗伊德邸，拥有制作人偶的能力。
题目翻译
爱丽丝收到一个含n个整数的数列作为她的生日礼物。因为她喜欢等差数列，她想把她的数列变成等差的。在一个等差数列中，一项和下一项之间的差值是一个常数。
她可以使用她的魔法力量，在一个数列上施法。她可以施展两种类型的法术。第一种类型是“增量法术”：当她使用这个法术时，她可以在这个数列中选择一个数字，并将这个数字加1。另一种类型，你已经猜到了，是“减量法术”：她可以选择一个数字，然后把这个数字减1。释放任何一种法术都会让她消耗1法力值。
现在她想知道最少需要消耗多少法力值，才能让她的数列变成等差的。
数据量：n不超过
2
×
1
0
5
2×10^{5}
2×105，
a
i
a_{i}
ai?不超过
1
0
13
10^{13}
1013。
思路
首先需要知道一个模型——货舱选址问题。
货舱选址问题
在一条数轴上有n家商店，坐标a1到an。现在需要在数轴上建立一家货舱，每天清晨，从货舱到每家商店都要运送一车商品。为了提高效率，求把货舱建在何处，可以使得货舱到每家商店的距离之和最小。
假设这个货舱地址选在x处，此时的距离之和为：
∣
a
1
?
x
∣
+
∣
a
2
?
x
∣
+
…
…
+
∣
a
n
?
x
∣
|a1-x|+|a2-x|+……+|an-x|
∣a1?x∣+∣a2?x∣+……+∣an?x∣。
由绝对值不等式得：
∣
a
?
x
∣
+
∣
b
?
x
∣
≥
∣
(
a
?
x
)
?
(
b
?
x
)
∣
=
∣
a
?
b
∣
|a-x|+|b-x|≥|(a-x)-(b-x)|=|a-b|
∣a?x∣+∣b?x∣≥∣(a?x)?(b?x)∣=∣a?b∣。设a≤b，则当a≤x≤b时，|a-x|+|b-x|取得最小值|a-b|。
先设a1≤a2≤……≤an-1≤an。
①若n为奇数，则
∣
a
1
?
x
∣
+
∣
a
2
?
x
∣
+
…
…
+
∣
a
n
?
x
∣
≥
∣
a
1
?
a
n
∣
+
∣
a
2
?
a
n
?
1
∣
+
…
…
+
∣
a
(
n
+
1
)
/
2
?
x
∣
|a1-x|+|a2-x|+……+|an-x|≥|a1-an|+|a2-an-1|+……+|a(n+1)/2-x|
∣a1?x∣+∣a2?x∣+……+∣an?x∣≥∣a1?an∣+∣a2?an?1∣+……+∣a(n+1)/2?x∣，当
a
1
≤
a
2
≤
…
…
≤
x
≤
…
…
≤
a
n
?
1
≤
a
n
a1≤a2≤……≤x≤……≤an-1≤an
a1≤a2≤……≤x≤……≤an?1≤an，且
∣
a
(
n
+
1
)
/
2
?
x
∣
=
0
|a(n+1)/2-x|=0
∣a(n+1)/2?x∣=0，即
x
=
a
(
n
+
1
)
/
2
x=a(n+1)/2
x=a(n+1)/2时取得最小值。
②若n为偶数，则
∣
a
1
?
x
∣
+
∣
a
2
?
x
∣
+
…
…
+
∣
a
n
?
x
∣
≥
∣
a
1
?
a
n
∣
+
∣
a
2
?
a
n
?
1
∣
+
…
…
+
∣
a
n
/
2
?
a
n
/
2
+
1
∣
|a1-x|+|a2-x|+……+|an-x|≥|a1-an|+|a2-an-1|+……+|an/2-an/2+1|
∣a1?x∣+∣a2?x∣+……+∣an?x∣≥∣a1?an∣+∣a2?an?1∣+……+∣an/2?an/2+1∣，当
a
1
≤
a
2
≤
…
…
≤
x
≤
…
…
≤
a
n
?
1
≤
a
n
a1≤a2≤……≤x≤……≤an-1≤an
a1≤a2≤……≤x≤……≤an?1≤an，即
a
n
/
2
≤
x
≤
a
n
/
2
+
1
an/2≤x≤an/2+1
an/2≤x≤an/2+1时取得最小值。
结论：n为奇数，x取所有商店地址的中位数可令不等式最小；n为偶数，x取所有商店地址的两个中位数之间（包含两个中位数）都可令不等式最小。
类比推导
知道了货舱选址模型后，进行如下推导：
设原数列为a，等差数列的公差为x，首项为未知量c1。则新数列的每一项为
c
i
=
c
1
+
(
i
?
1
)
x
ci=c1+(i-1)x
ci=c1+(i?1)x，故整体的操作数为
Σ
∣
a
i
?
[
c
1
+
(
i
?
1
)
x
]
∣
=
Σ
∣
[
a
i
?
(
i
?
1
)
x
]
?
c
1
∣
Σ|ai-[c1+(i-1)x]|=Σ|[ai-(i-1)x]-c1|
Σ∣ai?[c1+(i?1)x]∣=Σ∣[ai?(i?1)x]?c1∣，令
t
i
=
a
i
?
(
i
?
1
)
x
ti=ai-(i-1)x
ti=ai?(i?1)x，问题转化为求
Σ
∣
t
i
?
c
1
∣
Σ|ti-c1|
Σ∣ti?c1∣的最小值，即货舱选址模型。
但是我们不知道公差x是多少，也就无法确定数列t的每一项是多少。由于c1取多少与数列t有关，因此最小值仅取决于公差x。设令序列变为等差的最小代价为f(x)，下面先证明f(x)是下凸函数。
下凸函数证明
对于每个位置，消耗的魔力满足
∣
[
a
i
?
(
i
?
1
)
(
x
+
1
)
]
?
c
1
∣
+
∣
[
a
i
?
(
i
?
1
)
(
x
?
1
)
]
?
c
1
∣
=
∣
[
a
i
?
(
i
?
1
)
x
?
c
1
]
?
(
i
?
1
)
∣
+
∣
[
a
i
?
(
i
?
1
)
x
?
c
1
]
+
(
i
?
1
)
∣
≥
∣
[
a
i
?
(
i
?
1
)
x
?
c
1
]
?
(
i
?
1
)
+
[
a
i
?
(
i
?
1
)
x
?
c
1
]
+
(
i
?
1
)
∣
=
∣
2
?
[
a
i
?
(
i
?
1
)
x
?
c
1
]
∣
=
2
?
∣
[
a
i
?
(
i
?
1
)
x
]
?
c
1
∣
|[ai-(i-1)(x+1)]-c1|+|[ai-(i-1)(x-1)]-c1|=|[ai-(i-1)x-c1]-(i-1)|+ |[ai-(i-1)x-c1]+(i-1)|≥|[ai-(i-1)x-c1]-(i-1)+ [ai-(i-1)x-c1]+(i-1)|=|2*[ai-(i-1)x-c1]|= 2*|[ai-(i-1)x]-c1|
∣[ai?(i?1)(x+1)]?c1∣+∣[ai?(i?1)(x?1)]?c1∣=∣[ai?(i?1)x?c1]?(i?1)∣+∣[ai?(i?1)x?c1]+(i?1)∣≥∣[ai?(i?1)x?c1]?(i?1)+[ai?(i?1)x?c1]+(i?1)∣=∣2?[ai?(i?1)x?c1]∣=2?∣[ai?(i?1)x]?c1∣，对两侧求和，得
Σ
∣
[
a
i
?
(
i
?
1
)
(
x
+
1
)
]
?
c
1
∣
+
Σ
∣
[
a
i
?
(
i
?
1
)
(
x
?
1
)
]
?
c
1
∣
≥
2
?
Σ
∣
[
a
i
?
(
i
?
1
)
x
]
?
c
1
∣
Σ|[ai-(i-1)(x+1)]-c1|+Σ|[ai-(i-1)(x-1)]-c1|≥2*Σ|[ai-(i-1)x]-c1|
Σ∣[ai?(i?1)(x+1)]?c1∣+Σ∣[ai?(i?1)(x?1)]?c1∣≥2?Σ∣[ai?(i?1)x]?c1∣，即
f
(
x
+
1
)
+
f
(
x
?
1
)
≥
2
?
f
(
x
)
f(x+1)+f(x-1)≥2*f(x)
f(x+1)+f(x?1)≥2?f(x)，证得f(x)是下凸函数。
下凸函数是单谷函数，只有一个极小值，即最小值。也就是说，令f(x)取得最小值对应的x是唯一的。由于原数列中每个元素的值在
?
1
0
13
-10^{13}
?1013到
1
0
13
10^{13}
1013之间，因此x的定义域为这个区间，只需要在这个区间内求这个下凸函数的极小值点。解决此类问题的常用方法是三分法，它是二分法的一个变形。
三分法
三分法有左中点midl，右中点midr，左端点left，右端点right四个边界值，把整个查找区间分成三份。其中 m i d l = l e f t + ( r i g h t ? l e f t ) / 3 midl=left+(right-left)/3 midl=left+(right?left)/3， m i d r = r i g h t ? ( r i g h t ? l e f t ) / 3 midr=right-(right-left)/3 midr=right?(right?left)/3。对于下凸函数，如果a[midr]==a[midl]就是找到了；如果a[midl]<a[midr]，令right=midr-1；如果a[midl]>a[midr]，令left=midl+1。如此，端点不断向极小值点靠拢，就可以得到最终答案。
细节
货舱选址时，数列t的中位数必须在O(n)的时间复杂度内计算得出，就只能用nth_element(t+1,t+(n+1)/2,t+1+n)计算。否则用sort排序会超时；另外，由于单个元素的值达到了 1 0 13 10^{13} 1013，整个数列最多有 2 × 1 0 5 2×10^{5} 2×105个元素，每次累加答案时二者相乘会爆掉long long，因此只能开__int128。__int128只能用devcpp编译，并且对于cin，cout，scanf，printf都会报错，只能自己写快读快输函数。由于对abs也会报错，abs也要自己写，但对nth_element不会报错。
代码
#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], t[maxn], n;
int read() {
char c = getchar(); int f = 1, x = 0;
while (c<'0' || c>'9') { f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
return x*f;
}
void write(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9)write(x / 10);
putchar((x % 10) ^ 48);
}
int f(int x) {
int ans = 0;
for (int i = 1; i <= n; i++)t[i] = a[i] - (i - 1)*x;
nth_element(t + 1, t + (n + 1) / 2, t + 1 + n);
int mid = t[(n + 1) / 2];
for (int i = 1; i <= n; i++) {
if (t[i] > mid)ans += (t[i] - mid);
else ans += (mid - t[i]);
}
return ans;
}
signed main()
{
n = read();
for (int i = 1; i <= n; i++)a[i] = read();
int left = -1e13, right = 1e13;
while (left < right) {
int midl = left + (right - left) / 3;
int midr = right - (right - left) / 3;
if (f(midl) <= f(midr)) { right = midr - 1; }
else left = midl + 1;
}
write(f(left));
return 0;
}
感想
本题难在细节之处过多，可谓是综合了很多细节。首先是要知道货舱选址模型；其次是要会用绝对值不等式证明凸函数；然后是要知道三分法求极值点；还要知道nth_element函数；最后要知道__int128，并且知道报错是因为没有写快读快输函数和用了abs函数。此题算是令我大开眼界了。
C 最佳策略
命题人
jiangly
题目背景
Ena：全名Shinonome Ena，即东云绘名，是《世界计划 彩色舞台》及其衍生作品的登场角色。
Mizuki：全名Mizuki Nana，即水树奈奈，日本女性配音演员、歌手、电台主持人。曾饰演日本动画《地狱少女》系列作品中的女性角色柴田鶫。也是由泽野弘之创作的“核爆神曲”《aLIEz》的原唱。
题目翻译
东云绘名和水树奈奈正在玩一个游戏。
在她们面前有n个物品，编号1到n。第i个物品的值是ai。东云绘名和水树奈奈轮流行动，东云绘名先手。每一次行动，玩家选择一个没有被拿走的物品并拿走。游戏在所有物品都被拿走时结束。每个玩家的目标是最大化她们拿走的物品的总价值。
确定两个玩家都采取最优行动，有多少种可能的游戏过程？这个数字也许很大，你应该输出它对998244353取模。
如果存在某个整数i（1≤i≤n）使得在第i次行动中拿走的物品的编号不同，就认为两个过程是不同的。
数据范围：
1
≤
n
≤
1
0
6
，
1
≤
a
i
≤
n
1≤n≤10^{6}，1≤a_{i}≤n
1≤n≤106，1≤ai?≤n。
思路
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e6 + 5;
int dp[maxn], a[maxn], cnt[maxn], sum[maxn], jc[maxn], inv_jc[maxn], n;
int quick_pow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1)ans = ans*a%mod;
a = a*a%mod;
b = b >> 1;
}
return ans;
}
void init() {
jc[0] = 1;
for (int i = 1; i <= n; i++) {
jc[i] = jc[i - 1] * i%mod;
inv_jc[i] = quick_pow(jc[i], mod - 2);
}
}
int C(int n, int m) {
if (m == 0)return 1;
return ((jc[n] * inv_jc[m] % mod) *inv_jc[n - m]) % mod;
}
signed main()
{
cin >> n;
init();
for (int i = 1; i <= n; i++)cin >> a[i], cnt[a[i]]++;
for (int i = 1; i <= n; i++)sum[i] = sum[i - 1] + cnt[i];
bool flag = false;
for (int i = 1; i <= n; i++) {
if (cnt[i] == 0)dp[i] = dp[i - 1];
else if (flag == false) {
flag = true;
dp[i] = 1;
for (int j = 2; j <= cnt[i]; j++)dp[i] = dp[i] * j%mod;
}
else {
dp[i] = dp[i - 1] * C(sum[i - 1] + cnt[i] / 2, cnt[i] / 2) % mod;
for (int j = 2; j <= cnt[i]; j++)dp[i] = dp[i] * j%mod;
}
}
cout << dp[n] << endl;
return 0;
}
感想
这就是一道披着博弈论外衣的动态规划题。其实观察数据量可以发现每个元素的大小都在 1 0 6 10^{6} 106以内，就可以推测出应该以元素大小为依据，从小到大进行dp递推，而不是从博弈论或贪心的角度考虑，从大到小。恰恰是博弈论和贪心蒙蔽了这道题动态规划的本质。其次就是奇数偶数问题，这非常好理解，对于当前考虑的最大值来说，偶数一定配对，奇数一定先手先选以保证最优。上述两点考虑之后，就可以根据插空法推出的组合计算公式计算了。依旧是用快速幂和费马小定理即可解决问题，同时注意C(n,0)==1就OK了。
总结
关于出题人
这次比赛延续了网络赛预赛的传统，每一道题目都取自二次元背景，可以说北大的诸位ACMer也是动画爱好者了。网络赛充斥着原神的题目，济南站由jiangly老师出的题目都与音游《世界计划 彩色舞台》有关，可以说老师也是音游爱好者了。但是比赛的时候没有注意到Kanade是立华奏就属于是我的一大失误了。经知乎证实，爱丽丝竟取材于《东方project》，可以说这延续了各位出题者喜欢对爱丽丝室友帕秋莉出题的传统了。
反思
由于水平有限，时间精力不足，我的第一场区域赛，也就是济南站，只能补这4道铜银题，金牌题实在是心有余而力不足。实际比赛能做出这4道题可以刚好拿到金牌。希望下次昆明站能够拿到铜牌吧。