Now we start to describe a kind of directed graph called the Drying Rack Graph (DRG) with a parameter N.
A DRG contains N groups of vertexes. The i-th group ViV^iVi contains 2N vertices: V1i,V2i,??,V2NiV^i_1, V^i_2, \cdots, V^i_{2N}V1i?,V2i?,?,V2Ni?.
There are two types of edges in DRG: intra-group edges (edges inside each group) and inter-group edges (edges between groups).
Intra-Group Edge: For the i-th group, the following intra-group edges exist:
(Vji,Vj+Ni)(V^i_j, V^i_{j+N})(Vji?,Vj+Ni?), for all integer j such that 1≤j≤N1 \le j \le N1≤j≤N;
(Vji,Vj+1i)(V^i_j, V^i_{j+1})(Vji?,Vj+1i?), for all integer j such that 1≤j≤N?11 \le j \le N-11≤j≤N?1 or N+1≤j≤2N?1N + 1 \leq j \le 2N-1N+1≤j≤2N?1.
Inter-Group Edge: The following inter-group edges exist:
(Vi+N1,V1i+1)(V^1_{i+N}, V^{i+1}1)(Vi+N1?,V1i+1?), for all integer i such that 1≤i≤N?11 \le i \le N - 11≤i≤N?1;
(Vi1,V1+Ni)(V^1{i}, V^{i}_{1+N})(Vi1?,V1+Ni?), for all integer i such that 2≤i≤N2 \le i \le N2≤i≤N.
Now we want to know the number of topo-order of a DRG parameterized with N.
A topo-order of a directed graph G=(V, E) is a permutation vp1,vp2,??,vp∣V(G)∣v_{p_1}, v_{p_2}, \cdots, v_{p_{|V(G)|}}vp1??,vp2??,?,vp∣V(G)∣?? of all vertices from V(G) such that for all i < j, (vpj,vpi)∈?E(G)(v_{p_j}, v_{p_i}) \not\in E(G)(vpj??,vpi??)??∈E(G)
In order to avoid calculations of huge integers, report answer modulo a prime M instead.
输入描述:
The input contains only two integers N, M (1≤N≤3000,N?N?2<M≤230)(1 \le N \le 3000, NN2 < M \le 2^{30})(1≤N≤3000,N?N?2<M≤230), and M is a prime.
输出描述:
Output one integer indicating the answer.
#include<bits/stdc++.h>
using namespace std;
long long a[18000010],b[18000010];
int dp[3010][3010],g[3010][3010],w[3010][3010],ans[3010],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]=1;a[1]=1;b[0]=1;b[1]=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=dp[0][j-1];else y=ans[0];x=(j-1)*(n*2+1)-n*2;(dp[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]=dp[i-1][i+1]+g[i][n];if(ans[i]>=mod) ans[i]-=mod;for(j=2;j<=n;j++){dp[i][j]=dp[i-1][j];if(j-1>i+1) y=dp[i][j-1];else y=ans[i];x=i+(j-1)*(n*2+1)-n*2;(dp[i][j]+=1ll*w[n][n]*y%mod*get(x+n*2,n*2)%mod)%=mod;}}printf("%d\n",ans[n-1]);return 0;
}