CF2066D2 Club of Young Aircraft Builders (hard version)题解

· · 题解

My blog。

请先读一下这篇文章。

书接上文，我们只需要稍微动下小手术即可。

我们考虑对于 dp_{i,j,k}，依旧枚举 p（定义与上文一致），我们要求小于等于 j 的时间中，有恰好 c 个大于等于 i 的飞机，而 [p+1,j] 又全是大于等于 i 的，且 [1,j] 中有一些已经确定的位置大于等于 i，我们记这个值为 q（可以容易前缀和预处理），则 [1,p] 中一定恰有 c-q-j+p+pp 个，其中 pp 为 [1,p] 中大于等于 i 的数量。

在 p 的变化过程中，pp 也在变化，所以我们需要对前缀和做下小手术。

如果我们这一次用 dp_{i-1,p,kk} 转移：

另外，在 dp_{i,j,k} 中，如果 j 时刻后面有第 i 层发出的飞机（可以预处理），根据题意，需要将这个状态特判为 0。

依旧优雅~

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,c,m,a[10005];
int dp[10005][105],dpp[10005][105],s[10005][105];
int ksm(int x,int y)
{
    if(y==1) return x;
    if(!y) return 1;
    int mid=ksm(x,y>>1);
    if(y&1) return mid*1ll*mid%mod*x%mod;
    return mid*1ll*mid%mod;
}
int jie[10005],njie[10005];
int C(int x,int y)
{
    if(x<y) return 0;
    return jie[x]*1ll*njie[y]%mod*njie[x-y]%mod;
}
int q[10005][105],h[10005][105];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    jie[0]=1,njie[0]=1;
    for(int i=1;i<=10000;i++) jie[i]=jie[i-1]*1ll*i%mod,njie[i]=ksm(jie[i],mod-2);
    cin>>t;
    while(t--)
    {
        cin>>n>>c>>m;
        for(int i=1;i<=m;i++) cin>>a[i];
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
                if(j<=a[i]) q[i][j]=(q[i-1][j]+1)%mod;
                else q[i][j]=q[i-1][j];
        }
        for(int i=1;i<=n;i++) h[m+1][i]=0;
        for(int i=m;i>=1;i--)
        {
            for(int j=1;j<=n;j++)
                if(j==a[i]) h[i][j]=(h[i+1][j]+1)%mod;
                else h[i][j]=h[i+1][j];
        }
        for(int i=0;i<=c-q[c][1];i++) 
        {
            if(h[c+1][1]) continue ;
            dp[c][i]=C(c-q[c][1],i);
        }
        for(int j=1;j<=m;j++)
            for(int k=0;k<=c;k++) 
                if(a[j]) s[j][k]=(dp[j][k]+s[j-1][k])%mod;
                else s[j][k]=(dp[j][k]+s[j-1][k-1])%mod;
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(h[j+1][i]) continue ;
                for(int k=0;k<=c-q[j][i];k++)
                {
                    if(c-(j-j)-q[j][i]>=0)
                    dpp[j][k]=s[j][c-(j-j)-q[j][i]]*1ll*C(c-q[j][i],k)%mod;
                } 
            }
            for(int j=1;j<=m;j++)
                for(int k=0;k<=c;k++) dp[j][k]=dpp[j][k],dpp[j][k]=0;
            for(int j=1;j<=m;j++)
                for(int k=0;k<=c;k++) 
                    if(a[j]) s[j][k]=(dp[j][k]+s[j-1][k])%mod;
                    else s[j][k]=(dp[j][k]+s[j-1][k-1])%mod;
        }
        cout<<dp[m][0]<<"\n";
        for(int j=1;j<=m;j++)
            for(int k=0;k<=c;k++) dp[j][k]=0;
    }
    return 0;
}

::::