AGC046F Forbidden Tournament
syzf2222
·
·
题解
这个题是可以做的。
注意到一个竞赛图可以缩成链状，如果我们在非链底处存在一个三元环就寄了。
引理1：一个不小于 3 的 SCC 中必然存在三元环。
证明：考虑归纳。n=3 时显然。
若 $3\to 1$，则 $(1,2,3)$ 已经是三元环，否则把 $2$ 剔除仍是 SCC。
所以现在非链底的 SCC 都只能是单点了。
现在考虑最后一个 SCC,当然我们只讨论不是单点的情况。随便拉出一个单点 $x$。
**引理2：$x$ 的前驱和后继都形成一条链。**
证明：前驱是显然的，如果不是单点就必然有三元环了。设前驱的链顶为 $S$。
考虑后继。若不形成一个链，则在最后有一个 SCC。
如果这个 SCC 中所有点都是连向 $S$ 的，则这些中形成了要求的子图了。
否则一定存在两个非空集合 $S_1,S_2$，$S_1$ 中连向 $S$，$S_2$ 中被 $S$ 连向。
不存在 $a\in S_1,b\in S_2,a\to b$，否则 $(x,S,a,b)$ 为要求的子图。
故 $S_2\to S_1$，所以这不是 SCC！
现在考虑其前驱序列 $\{I_p\}$ 与后继集合 $\{O_q\}$ 的连边情况。
首先一定有 $O_q\to I_1$，因为要形成一个 SCC。
注意到每个 $I$ 向 $O$ 的连边一定是一个前缀是出边。否则如果 $\exists i<j,I_a\to O_j,O_i\to I_a$，则 $(I_a,O_i,x,O_j)$ 是要求的子图。
设 $P_i$ 为分界点，即 $\forall j\in [1,P_j],I_i\to O_j,j\in (P_i,q],O_j\to I_i$。
发现 $P$ 是不降的，否则 $\exists i,P_i>P_{i+1}$，则 $(I_i,O_{P_i},O_{P_i+1},I_{i+1})$ 是要求的子图。
但是显然这个条件显然要把 $P_i=q$ 排除在外，但是真的要排除在外吗？
若存在 $i<j,q=P_i>P_j$，则 $(I_1,O_q,I_i,I_j)$ 是要求的子图。
那么现在所有的情况都讨论完了，以上的条件就是充要的。
于是现在可以计算了。首先枚举一开始有多少个单点最为前缀，其次枚举在链底的 SCC 内有前驱大小，然后 $dp$ 连边情况。
设 $dp_{i,j}$ 表示 $P_i=j$ 的方案数，可以从 $dp_{i-1,k},k\leqslant j$ 处转移来。
注意 $dp_{i,j}$ 存在当且仅当 $I_i$ 和 $O_j$ 的度数都不超过限制，而这两个都可以 $O(1)$ 计算得到。
时间复杂度 $O(n^4)$。
```
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define inf 1e9
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=205;
int mod,C[N][N],fac[N],ans,dp[N][N];
inline int calc(int n,int m){
if(m<=0)return 0;int res=0;
for(int p=1;p<n-1;p++){
int q=n-1-p,sum=0;dp[1][q]=0;
if(max(p,q)>m)continue;
for(int i=0;i<q;i++){
dp[1][i]=1;
if(q-i>m)dp[1][i]=0;
if(i&&p+i>m)dp[1][i]=0;
}for(int i=2;i<=p;i++)
for(int j=0,S=0;j<=q;j++){
S=(S+dp[i-1][j])%mod,dp[i][j]=S;
if(i-1+q-j>m)dp[i][j]=0;
if(j&&p-i+1+1+j-1>m)dp[i][j]=0;
}
for(int i=0;i<=q;i++)
sum=(sum+dp[p][i])%mod;
res=(res+1ll*C[n-1][p]*fac[p]%mod*fac[q]%mod*sum)%mod;
}return res;
}
int n,m;
int main(){
n=read(),m=read(),mod=read();
fac[0]=C[0][0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}if(m==n-1)ans=fac[n];
for(int i=0;i<=n-3;i++)
ans=(ans+1ll*fac[i]*C[n][i]%mod*calc(n-i,m-i))%mod;
printf("%d\n",ans);
return 0;
}
```
深深地感到自己的弱小。