题目大意
原题长的一批的翻译：
有一种有向图，被称为排列的DRG图，其包含
组节点，第
组
包含
个节点：
。
DRG上有2种边：组内边和组间边。
第组内的组内边可以表示为：（应该都能看懂）
组间边可以表示为：
现在我们想知道排列的DRG图的拓扑序列的数量。
有向图的拓扑序列可以表示为：
。
所有节点来自且对于任意
,
答案对素数取模。
简单的说
给定一个有向无环图-晒肉架图DRG(n)，求DRG(n)有多少种拓扑序列。
拓扑序列：
1.从图中选择一个没有前驱（即入度为0）的顶点并输出。
2.从图中删除该顶点（即加入拓扑序列）和所有以它为起点的有向边。
3.重复1,2，直到图为空或图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
解题思路
先来举例说明DRG图到底是个啥。这是DRG(4)的图，烤肉架图名不虚传：
略微观察一下，我们可以发现每个肉片只和架子的两个节点连接。当这两个节点被删除，肉片就会分离，而肉片作为一个子图的拓扑序列是非常容易计算的。
所以，本题做法要重点维护架子以及连在架子上的肉片的状态。
可以发现在按拓扑序列删除节点的过程中，这张图的特征可以分为以下三种情况：
h(n)
第一种是一个完整的DRG(n)只删除了第一个节点，我们设这样的情况为（在代码中因为是最后输出，改成了ans）。
是删了第一个节点，那么接下来只有两种删除方法，删去第一行的节点或者删去第一列的节点。
分别会变成以及
（往下看）。
f(i,j)
第二种是在完整的DRG(n)中删除了第一行中两个以上的连续节点，设第一行剩余节点数为，第二行节点数为
，我们设这种情况为f(i,j)。
接下来也只有两种删除方法，分别是变为
以及
，
中的其中一种（因为此时有一个肉片掉了）。
g(i,j)
第三种是在完整的DRG(n)中删除了第一行和第二行的第一个节点，然后连续删除了第一块肉片的左半边部分。设第一行的剩余节点数为，以及第一块肉片左半边剩余节点数
，我们设这种情况为g(i,j)。
也只有两种删除操作，分别是变成
以及
（肉片掉了）。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=3010,M=18000010;
long long a[M],b[M];
int f[N][N],g[N][N],w[N][N],ans[N],n,m,mod;
int get(int x,int y)
{
return a[x]*b[y]%mod*b[x-y]%mod;
}
int main()
{
int x,y,i,j;
scanf("%d%d",&n,&mod);
m=n*n*2,a[0]=a[1]=b[0]=b[1]=ans[0]=1;
for(i=2;i<=m;i++)
a[i]=a[i-1]*i%mod,b[i]=mod-(mod/i)*b[mod%i]%mod;
for(i=1;i<=m;i++)
b[i]=b[i-1]*b[i]%mod;
for(i=0;i<=n;i++)
for(j=i;j<=n;j++)
{
if(i==0) w[i][j]=1;
else
{
w[i][j]=w[i-1][j];
if(i<j) w[i][j]+=w[i][j-1];
if(w[i][j]>=mod) w[i][j]-=mod;
}
}
for(j=2;j<=n;j++)
{
if(j>=3) y=f[0][j-1];
else y=ans[0];
x=(j-1)*(n*2+1)-n*2;
(f[0][j]+=1ll*w[n][n]*y%mod*get(x+n*2,n*2)%mod)%=mod;
}
for(i=1;i<n;i++)
{
for(j=0;j<=n;j++)
{
x=2*i-1+(i-1)*(n*2);
g[i][j]=1ll*w[j][n]*ans[i-1]%mod*get(n+j+x,x)%mod;
if(j!=0) (g[i][j]+=g[i][j-1])%=mod;
}
ans[i]=f[i-1][i+1]+g[i][n];
if(ans[i]>=mod) ans[i]-=mod;
for(j=2;j<=n;j++)
{
f[i][j]=f[i-1][j];
if(j-1>i+1) y=f[i][j-1];
else y=ans[i];
x=i+(j-1)*(n*2+1)-n*2;
(f[i][j]+=1ll*w[n][n]*y%mod*get(x+n*2,n*2)%mod)%=mod;
}
}
printf("%d\n",ans[n-1]);
return 0;
}
京公网安备 11010502036488号