2020牛客暑期多校训练营（第七场） Topo Counting_综合

原题
题目描述
在这里插入图片描述
样例1
输入

2 1073741789

输出

样例2
输入

3 1073741789

输出

思路
我们一拍脑袋，因为 $n≤3000$ ，~~似乎没有后效性，似乎求得是最优解~~ ，所以盲猜这是一道 $dp$ 。
我们会发现每个肉片只受制于架子上的两个节点，所以本题的核心做法就是维护架子以及连在架子上的肉片的形态。
在状态转移时大致会有以下 $3$ 种情况 $：$

第一种是一个完整的 $DRG(n)$ 只删除了第一个节点,，设为 $h(n)$ 。对于 $h(n)$ ，接下来有两种删除方法, 分别会变成 $f(n–2，n)$ 以及 $g(n–1，n)$ 。
第二种是在一个完整的 $DRG(n)$ 中删除了第一行中两个以上的连续节点，这类形态有第一行中剩余节点数 $i$ 和第二行的节点数 $j$ 控制，设为 $f(i，j)$ 。对于 $f(i，j)$ ，接下来也有两种删除方法,，分别会变成 $f(i–1，j)$ 以及 $(f(i,j–1)$ 和 $h(j–1)$ 中的其中一种 $+$ 一个分离出去的完整肉片)。
第三种是在一个完整的 $DRG(n)$ 中删除了第一行和第二行的第一个节点，然后连续删除了第一块肉片的左半边部分,，这类形态由架子上第一行的剩余节点数 $i$ 以及第一块肉片左半边剩余节点数 $j$ 控制，设为 $g(i,j)$ 。对于 $g(i,j)$ 也有两种情况，分别变成 $g(i,j–1)$ 以及 $h(i)+$ 分离出去的一个肉片。

这样的时间复杂度是 $O($ $n$ ² $)$ ，可以过。具体细节可以看以下代码。
代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3005,maxx=18e6+5;
ll n,mx,mod,u[maxx],v[maxx],h[maxn],dp[maxn][maxn];
int ksm(ll a,ll b){int k=1;while(b){if(b&1)k=k*a%mod;b>>=1;a=a*a%mod;}return k;}
int C(int a,int b){if(a<b||b<0) return 0;return 1ll*u[a]*v[b]%mod*v[a-b]%mod;}
int CC(int a,int b){return (C(2*a-b,a)-C(2*a-b,a-b-1)+mod)%mod;}
int main()
{scanf("%lld%lld",&n,&mod);u[0]=dp[0][0]=1;mx=2*n*n-2;for(int i=1;i<maxx;i++)u[i]=u[i-1]*i%mod;v[maxx-1]=ksm(u[maxx-1],mod-2);for(int i=maxx-2;~i;i--)v[i]=v[i+1]*(i+1)%mod;for(int i=0;i<n;i++)for(int j=0,k=mx-min(i,j)*n*2-i-j;j<n;j++,k=mx-min(i,j)*n*2-i-j){if(i==j && j==n-1)continue;if(j==i+1)for(int v=0;v<=n;v++)dp[i+1][j]=(dp[i+1][j]+dp[i][j]*C(k-v,n*2-v)%mod*CC(n,v)%mod)%mod;else{dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;if(i==j)dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;else dp[i][j+1]=(dp[i][j+1]+dp[i][j]*C(k,n*2)%mod*CC(n,0)%mod)%mod;}     }printf("%lld",dp[n-1][n-1]);
}