[atAGC056F]Degree Sequence in DFS Order

（以下图默认均为$n$个点$,m$条边$,$无自环的无向连通图）

注意到点编号并没有意义，不妨强制dfs序为$\{1,2,...,n\}$，那么$\{a_{i}\}$合法等价于存在图$G$使得点$i$的度数为$a_{i}$且存在一种dfs序为$\{1,2,...,n\}$

称满足后者的图为"好图"，称$\forall i\in [2,n]$存在$j\in [1,i)$与$i$相邻的图为"半好图"，显然"好图"总是"半好图"

结论1：对于半好图$G$，存在好图$G'$使得$G$与$G'$所有点度数均相同

对于$G$中$1\le a

考虑$\sum_{(x,y)\in E}(y-x)^{2}$，注意到每次操作后该值单调递增且有$mn^{2}$这个上界，因此过程有限

对于最终得到的图为$G'$，不难证明其符合条件，即得证

换言之，不妨将$\{a_{i}\}$合法的条件中"$G$为好图"改为"$G$为半好图"

结论2：$\{a_{i}\}$合法当且仅当满足以下条件：

1.$\forall i\in [1,n],a_{i}\in Z^{+}$且$\sum_{i=1}^{n}a_{i}=2m$

2.$a_{1}\le m$且$\forall i\in [2,n],a_{i}\le m-(i-2)$

3.$\forall i\in [0,n),\sum_{j=1}^{i}a_{j}\ge 2i-1$

必要性：

1.关于第1个条件，两者均显然成立（前者对$i$是否为1分类讨论即可）

2.关于第2个条件，$[2,i)$这些点均要"向前"连一条边，进而$i$至多连$m-(i-2)$条边

另外，由于没有自环，显然有$a_{1}\le m$（上式仅得到$a_{1}\le m+1$）

3.关于第3个条件，$[1,i]$这些点内部有$2(i-1)$条边且$i+1$至少再连一条边，进而度数和$\ge 2i-1$

充分性：

对于$i\in [2,n]$，依次选择当前最大的$a_{j}$（其中$j\in [1,i)$，多个任选）并连边$(i,j)$（将$a_{i}$和$a_{j}$均减1）

此时即保证是"半好图"，进而仅需要保证$a_{i}\in [0,m']$且$\sum_{i=1}^{n}a_{i}=2m'$（其中$m'$为剩余边数）

1.对于$a_{i}\ge 0$，也即每一次$a_{i},a_{j}\ge 1$，$a_{i}$是第一次操作根据$a_{i}\in Z^{+}$显然，若$a_{j}=0$即$\sum_{j=1}^{i-1}a_{j}=0$，由于之前已经选了$i-1$条边，可得初始$\sum_{j=1}^{i-1}a_{j}\le 2i-2$，与3矛盾

2.对于$a_{i}\le m'$，若存在$a_{j}>m'$，则在$i\in (j,n]$时必然都选该$a_{j}$（若还操作过$k$，最终$a_{k}\ge a_{j}-1$，那么$a_{j}+a_{k}>2m'$与3矛盾），而其仍然$>m'$，与2矛盾

3.对于$\sum_{i=1}^{n}a_{i}=2m'$，根据初始$\sum_{i=1}^{n}a_{i}=2m$显然成立

进一步的，构造$b_{i}=\begin{cases}a_{1}&(i=0)\\a_{i+1}-1&(1\le i

对于$b_{i}$而言，结论2中的条件即等价于：

1.$\forall i\in [0,n),b_{i}\in N$且$\sum_{i=0}^{n-1}b_{i}=2m-(n-1)$

2.$\forall i\in [0,n),b_{i}\le m-i$

3.$\forall i\in [0,n),\sum_{j=0}^{i-1}b_{j}\ge i$

（关于$b_{0}=a_{1}\in Z^{+}$的条件已经在3中保证）

结论3：在保证第1和3个条件的基础上，至多存在一个$i$不满足第2个条件

反证法，若存在$x

换言之，先忽略第2个条件，再枚举对应的$i$减去不满足第2个条件的方案

关于前半部分，即求$(0,0)\rightarrow (n-1,2m-(n-1))$（仅能向上或向右）且不经过$y

类似卡特兰数的推导，将第一处经过后的部分沿$y=x-1$?翻折，翻折后的终点即$(2m-(n-2),n-2)$，经过该处必然经过$y

关于后半部分，将$b_{i}$减去$m-i+1$，第1个条件变为$\sum_{i=0}^{n-1}b_{i}=m-n+i$，且$i$之后第3个条件必然成立

特判$i=0$的情况，此时答案显然为${m-1\choose n-1}$

对于$i\ge 1$的情况，考虑路径中第一次经过$(*,i)$的位置，并枚举第一维$k\in [0,i)$，之后的路径即没有限制，结合前者对应答案即为$\left({k+i-1\choose k}-{k+i-1\choose k-1}\right){m-k-1\choose m-n}$

调换两者枚举顺序，右式与$i$无关，左式根据$\sum_{i=l}^{r}{i\choose k}={r+1\choose k+1}-{l\choose k+1}$可以$o(1)$计算

时间复杂度为$o(m)$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 2000005
 4 #define mod 998244353
 5 #define ll long long
 6 int n,m,ans,fac[N],inv[N];
 7 int C(int n,int m){
 8     if ((m<0)||(nreturn 0;
 9     return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
10 }
11 int main(){
12     scanf("%d%d",&n,&m);
13     fac[0]=inv[0]=inv[1]=1;
14     for(int i=1;i1]*i%mod;
15     for(int i=2;imod;
16     for(int i=1;i1]*inv[i]%mod;
17     ans=(C((m<<1),n-1)-C((m<<1),n-2)+mod)%mod;
18     ans=(ans-C(m-1,n-1)+mod)%mod;
19     for(int k=0;k){
20         int s=(C(k+n-1,k+1)-C((k<<1),k+1)+mod)%mod;
21         s=(s-(C(k+n-1,k)-C((k<<1),k)+mod)%mod)%mod;
22         ans=(ans-(ll)s*C(m-k-1,m-n)%mod+mod)%mod;
23     }
24     printf("%d\n",ans);
25     return 0;
26 }