当前位置: 代码迷 >> 综合 >> 2020牛客暑期多校训练营(第七场) Topo Counting
  详细解决方案

2020牛客暑期多校训练营(第七场) Topo Counting

热度:4   发布时间:2024-02-06 08:24:55.0

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

2 1073741789

输出

31

样例2
输入

3 1073741789

输出

7954100

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

  • 第一种是一个完整的 D R G ( n ) DRG(n) 只删除了第一个节点,,设为 h ( n ) h(n) 。对于 h ( n ) h(n) , 接下来有两种删除方法, 分别会变成 f ( n 2 n ) f(n–2,n) 以及 g ( n 1 n ) g(n–1,n)
    在这里插入图片描述
  • 第二种是在一个完整的 D R G ( n ) DRG(n) 中删除了第一行中两个以上的连续节点,这类形态有第一行中剩余节点数 i i 和第二行的节点数 j j 控制,设为 f ( i j ) f(i,j) 。对于 f ( i j ) f(i,j) ,接下来也有两种删除方法,,分别会变成 f ( i 1 j ) f(i–1,j) 以及 ( f ( i , j 1 ) (f(i,j–1) h ( j 1 ) h(j–1) 中的其中一种 + + 一个分离出去的完整肉片)。
    在这里插入图片描述
  • 第三种是在一个完整的 D R G ( n ) DRG(n) 中删除了第一行和第二行的第一个节点, 然后连续删除了第一块肉片的左半边部分,,这类形态由架子上第一行的剩余节点数 i i 以及第一块肉片左半边剩余节点数 j j 控制,设为 g ( i , j ) g(i,j) 。对于 g ( i , j ) g(i,j) 也有两种情况,分别变成 g ( i , j 1 ) g(i,j–1) 以及 h ( i ) + h(i)+ 分离出去的一个肉片。
    在这里插入图片描述
    这样的时间复杂度是 O ( O( n n 2 ) ) ,可以过。具体细节可以看以下代码。
    代码
#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]);
}