本文最后编辑于 前，其中的内容可能需要更新。
加训以来打的最艰难的一场，同时也是最难补题的一场，只能说欧洲的题目风格和中国还是差别不小，尤其是代码实现上的难度。
A. Alice the Fan
dp打表。19徐州打铁的教训：能暴力就不要分类讨论。
考虑$f_{a,b,c,d}$表示当前大比分为$a:b$，小比分为$c:d$时是否可行（用bool类型存储），状态数共$3\times3\times200\times200$种。预处理出一局种合法的小比分情况，显然少于$400$种，因此可以$O(400)$进行dp时转移，总复杂度大概$O(1.2\times10^8)$，同时开一个数组记录$dp$转移的路径以输出答案。
B. Bitmatching
C. Cactus Search
仙人掌背景的交互题，待补。
D. Distance Sum
E. Easy Chess
签到。
F. Fractions
G. Guest Student
签到。
H. Harder Satisfiability
I. Interval-Free Permutations
计数，析合树。
题解待补充。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400+7;
int n,p;
ll fac[N],f[N],g[N][N],h[N];
ll qpow(ll a,ll n=p-2,ll m=p){
ll res=1;
a%=m;
while(n){
if(n&1)res=res*a%m;
a=a*a%m,n>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
int T=1;
n=400;
cin>>T>>p;
f[1]=fac[0]=g[0][0]=1;
f[2]=2;
for(int i=1;i<N;i++){
fac[i]=fac[i-1]*i%p;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
for(int k=1;k<=i;k++){
g[i][j]=(g[i][j]+g[i-k][j-1]*fac[k]%p)%p;
}
}
}
for(int i=1;i<=n;i++){
h[i]=fac[i];
for(int j=1;j<i;j++){
h[i]=(h[i]-h[j]*fac[i-j]%p+p)%p;
}
}
for(int i=3;i<=n;i++){
f[i]=fac[i];
for(int j=1;j<i;j++){
f[i]=(f[i]-h[j]*2%p*fac[i-j]%p+p)%p;
}
for(int j=4;j<i;j++){
f[i]=(f[i]-g[i][j]*f[j]%p+p)%p;
}
}
while(T--){
cin>>n;
cout<<f[n]<<"\n";
}
}
|
J. JS Minification
K. King Kog’s Reception
L. Lazyland
签到。
M. Minegraphed
构造，模拟。赛中先tarjan缩点然后隔一层构造$3\times(2n+1)$的层，这层分三个部分，如图所示
1
2
3
| .............
#+#+#+#+#+#+#
.............
|
其中第$1,3$行为上层的落点和去往下层的洞，利用同层’+’的位置设置DAG的可达关系。
由于写起来过于模拟导致结束前5min才过，但是赛后发现好像有缩点都不用的简单写法，补完其它题学一下。