Preface

补题，这样一来军训这段时间口胡的题目就都写完了，后面空余的时间就优先做学校要求的专题了（主要是几何，因为字符串已经基本做完了）

唉现在的计数水平说实话练了这么多还是没有太大长进，有些巧妙的地方就是想不过去，所以打Atcoder就会很难受

不过相信多练总比不练好，可能到时候需要专门试着去总结一下计数题的套路和trick啥的

A - Ekiden Race

考虑如果\(i\)可能为答案，则必然不能存在一个\(j>i\)，满足\(p_i>p_j\)，因为这样\(j\)的返回速度一定比\(i\)快

因此答案就是所有值等于后缀最小值的位置数量

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i)	scanf("%d",&a[i]);
		int mi=1e9,ans=0; for (i=n;i>=1;--i) if (mi=min(mi,a[i]),mi==a[i]) ++ans;
		printf("%d\n",ans);
	}
	return 0;
}

B - Insertion Sort 2

首先简单手玩发现当逆序对数目为奇数时一定无解，否则一定有解

而构造答案的话我们考虑从前往后复原每个位置，如果\(a_i\ne i\)就把后面的\(i\)换到这一位上来

要注意如果\(i\)在位置\(n\)上，我们就需要先把最后两个数往前移一位再操作

举个例子比如当\(a=\{4,3,2,1\}\)时：

\[4,3,2,1\to4,2,1,3\to 1,3,4,2\to 1,4,2,3\to 1,2,3,4 \]

这也是为什么题目给出了\(2n\)次步数限制的原因

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,a[N],x[N<<1],y[N<<1],cnt,num;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=n;++i) for (j=1;j<i;++j) num+=a[j]>a[i];
	if (num&1) return puts("No"),0;
	for (i=1;i<=n;++i)
	{
		if (a[i]==i) continue;
		int pos; for (j=1;j<=n;++j) if (a[j]==i) { pos=j; break; }
		if (pos==n)
		{
			x[++cnt]=n-1; y[cnt]=n-3; int tmp=a[n-2];
			a[n-2]=a[n-1]; a[n-1]=a[n]; a[n]=tmp; pos=n-1;
		}
		x[++cnt]=pos; int t1=a[pos],t2=a[pos+1];
		for (j=pos;j<=n-2;++j) a[j]=a[j+2];
		y[cnt]=i-1; for (j=n-2;j>=i;--j) a[j+2]=a[j];
		a[i]=t1; a[i+1]=t2;
		//for (j=1;j<=n;++j) printf("%d%c",a[j]," \n"[j==n]);
	}
	for (printf("Yes\n%d\n",cnt),i=1;i<=cnt;++i) printf("%d %d\n",x[i],y[i]);
	return 0;
}

C - Mex Game on Tree

比较简单的思维题，首先要注意到第二个人加入数一定是加\(K\)是最优的，因为这样可以导致这个点的所有祖先一定不满足要求

然后我们很容易发现如果第一个人想获胜，就必须只操作\(0\)次或\(1\)次就获胜，不然第二个人总能想办法阻止掉

而这两种情况都比较简单，因为数据范围较小，可以直接暴力枚举每个点然后枚举其子树内所有点，简单讨论一下即可

感觉应该可以想办法做到\(O(n\times \operatorname{Poly}(\log n))\)的，不过没有细想了

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,n,k,x,a[N],bkt[N]; vector <int> v[N];
inline void DFS(CI now)
{
	++bkt[~a[now]?a[now]:n+1]; for (int to:v[now]) DFS(to);
}
inline int mex(int *bkt)
{
	int x=0; while (bkt[x]) ++x; return x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) v[i].clear();
		for (i=2;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
		for (i=1;i<=n;++i) scanf("%d",&a[i]);
		bool flag=0; for (i=1;i<=n&&!flag;++i)
		{
			for (j=0;j<=n+1;++j) bkt[j]=0; //-1->n+1
			if (DFS(i),!bkt[n+1]) flag=mex(bkt)==k;
			else if (bkt[n+1]==1)
			{
				if (bkt[k]) continue;
				for (j=0;j<k;++j) if (!bkt[j]) { bkt[j]=1; break; }
				flag=mex(bkt)==k;				
			}
		}
		puts(flag?"Alice":"Bob");
	}
	return 0;
}

D - Smallest Vertices

好题，不过因为我把Prufer序列这个东西忘完了所以第一步就无从下手了

一般对于这种边的选择是任意的树的个数统计（有边的限制的话就是矩阵树定理），尤其是和度数沾边的，都要考虑Prufer序列

但一般的Prufer序列都是针对无根树的，这里是以\(1\)为根的有根树怎么处理呢，很简单，我们修改定义要求每次选编号最大的节点删除，这样留下了的就一定是\(1\)号节点了

不过由于这里的度数的定义其实是出度，因此和一般情况还有点区别，具体地，满足题意的树的个数应该是：

\[\frac{(n-2)!}{(d_1-1)!\times \prod_{i=2}^nd_i!}\\ =\frac{(n-2)!\times d_1}{\prod_{i=1}^nd_i!} \]

然后考虑每个点的贡献，假设\(x\)是good的，那么它子树中的点\(y\)只能在\([x,n]\)中取

同时由于度数关系，设子树中的点集为\(S\)，则\(\sum_{y\in S} d_y=|S|-1\)

然后我们试着写出它的贡献表达式，注意这里前面一部分是子树内的方案数，后面一部分是子树外的方案数：

\[\frac{(|S|-2)!}{(d_x-1)!\times \prod_{y\in S,y\neq x}d_y!}\times\dfrac{(n-2-|S|+1)!}{(d_1-1)!\times \prod_{y\in S,y\neq x}d_y!}\\ =\dfrac{(n-1-|S|)!\times (|S|-2)!\times d_1\times d_v}{\prod_{i=1}^n d_i!} \]

不难发现计算答案只需要知道\(|S|\)即可，因此可以考虑DP，设\(f_{i,j,k}\)表示只用\(\ge i\)的点，其中选中的点的\(|S|=j\)，且\(\sum_{y\in S} d_y=k\)的方案数

转移的话就是一个类似背包的形式，不过要注意特殊处理\(1\)号点和所有叶结点，它们的贡献就是整体的方案数

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,mod=998244353;
int n,d[N],fact[N],ifac[N],f[N][N][N],all,mul=1,ans;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d",&n),init(n),i=1;i<=n;++i)
	scanf("%d",&d[i]),mul=1LL*mul*ifac[d[i]]%mod;
	for (all=1LL*fact[n-2]*mul%mod*d[1]%mod,f[n+1][0][0]=1,i=n;i>=1;--i)
	{
		for (j=1;j<=n;++j) for (k=d[i];k<=n;++k) inc(f[i][j][k],f[i+1][j-1][k-d[i]]);
		if (!d[i]||i==1) inc(ans,all); else
		for (j=2;j<=n;++j) inc(ans,1LL*f[i][j][j-1]*d[1]%mod*d[i]%mod*mul%mod*fact[n-1-j]%mod*fact[j-2]%mod);
		for (j=0;j<=n;++j) for (k=0;k<=n;++k) inc(f[i][j][k],f[i+1][j][k]);
	}
	return printf("%d",ans),0;
}

E - Strange Constraints

好题，Atcoder的计数题都只能直呼高妙

不妨设\(x_i\)表示序列\(B\)中等于\(i\)的位置的个数，则\(\sum_{i=1}^n x_i=n\)，且对于\(\forall i\in[1,n]\)，均满足\(x_i\le A_i\)

考虑第二个限制，其实就是把所有的\(x_i\)分配到\(A_j\ge x_i\)的位置上，我们考虑给\(x_i\)降序排序使其满足\(x_1\ge x_2\ge\cdots\ge x_n\)

同时如果我们记\(S(i)=\sum_{j=1}^n [a_j\ge i]\)，那么可以写出关于\(x_i\)的方案数表达式：

\[C_{S(x_1)}^{x_1}\times C_{S(x_2)-x_1}^{x_2}\times \cdots\times C_{S(x_n)-\sum_{j<n}x_j}^{x_n} \]

直观的想法就是对于每个位置的\(x_i\)讨论，虽然这样很容易满足\(x_i\le A_i\)的限制，但是却不能处理需要排序才能计算贡献的问题

那么我们这里就要想办法优先处理不好搞的这一块，我们考虑按照\(x_i\)从大到小的顺序来DP，同时我们发现原来要满足的\(x_i\le A_i\)的限制其实也很好处理

具体的，如果我们设\(f_{i,j,k}\)表示考虑了\(j\)个数，此时最小的数为\(i\)，所有已经考虑了的\(x\)的和为\(k\)的方案数

转移的话我们枚举\(x=i\)的个数\(t\)，则对于原来\(x_i\le A_i\)的限制，其实就是在\(S(i)-j\)个位置中选出\(t\)个来匹配

而后面那部分的系数可以拆开化简，具体地：

\[C_{S(i)-k}^{i}\times C_{S(i)-k-i}^{i}\times \cdots\times C_{S(i)-k-i\times (t-1)}^{i}\\ =\frac{(S(i)-k)!}{i!\times (S(i)-k-i)!}\times \frac{(S(i)-k-i)!}{i!\times (S(i)-k-2\times i)!}\times \cdots\times \frac{(S(i)-k-i\times(t-1))!}{i!\times (S(i)-k-i\times t)!}\\ =\frac{(S(i)-k)!}{(i!)^t\times (S(i)-k-i\times t)!} \]

那么转移的式子就很显然了：

\[f(i+1,j,k)\times C_{S(i)-j}^{t}\times\dfrac{(S(i)-k)!}{(i!)^t\times (S(i)-k-i\times t)!}\to f(i,j+l,k+i\times t) \]

总体复杂度乍一看是\(O(n^4)\)的，但冷静分析一下会发现复杂度其实是：

\[n^2\times\sum_{i=1}^n\dfrac{n^2}{i(i+1)}=O(n^3) \]

因此可以直接通过这题，不过要注意最后的答案应该是\(f_{-1,n,n}\)因为不能忽略\(x_i=0\)的贡献

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=505,mod=998244353;
int n,a[N],fact[N],ifac[N],f[2][N][N],g[N];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<m||n<0||m<0) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,t; for (scanf("%d",&n),init(n),i=1;i<=n;++i)
	scanf("%d",&a[i]),++g[a[i]]; for (i=n-1;i>=0;--i) g[i]+=g[i+1];
	int nw=0; f[nw][0][0]=1; for (i=n;i>=0;--i,nw^=1)
	{
		memset(f[nw^1],0,sizeof(f[nw^1])); int coef;
		for (j=0;j<=g[i];++j) for (k=0;k<=g[i];++k) if (f[nw][j][k])
		for (t=0,coef=1;k+i*t<=g[i]&&j+t<=g[i];++t,coef=1LL*coef*ifac[i]%mod)
		inc(f[nw^1][j+t][k+i*t],1LL*f[nw][j][k]*C(g[i]-j,t)%mod*fact[g[i]-k]%mod*coef%mod*ifac[g[i]-(k+i*t)]%mod);
	}
	return printf("%d",f[nw][n][n]),0;
}