CF301E Yaroslav and Arrangements

syzf2222 · 2021-04-29 21:24:59 · 题解

考虑dp，由于n,m,k\le 100，不妨多设几维状态。

想象一下，构造\text{good array}的过程实际上就是把最大的往次大的中间插空。

设dp[i][j][k][l]代表最大数为i，用了j个数，次大数有k个空隙，已经有l种方法。

枚举i+1的个数t，k\le t，不妨考虑次大数往最大数中插空。

每个空位只能加入一个次大数，故剩余t-k个空，方案数为C_{t-1}^{k-1}

故dp[i][j][k][l]\rightarrow dp[i+1][j+t][t-k][l*C_{t-1}^{k-1}]

方便起见，断环为链，设a[n+1]=a[1]，不妨设a[1]=1，结果乘以m-i+1即可。

初始条件：dp[0][0][1][1]=1

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 109
using namespace std;
int c[N][N],n,m,K,dp[2][N][N][N],ans;
void add(int &x,int y){x=(x+y>=mod)?x+y-mod:x+y;}
int main(){
    cin>>n>>m>>K;n++;
    c[0][0]=1;
    for(int i=1;i<=K;i++)
        for(int j=0;j<=i;j++){
            c[i][j]=(j?c[i-1][j-1]:0)+c[i-1][j];
            if(c[i][j]>K)c[i][j]=K+1;
        }
    int now=1,las=0;
    dp[now][0][1][1]=1;
    for(int i=1;i<=m;i++){
        las=now,now^=1;
        memset(dp[now],0,sizeof(dp[now]));
        for(int j=0;j<=n;j++)
            for(int k=1;k<=n;k++)
                for(int l=1;l<=K;l++)
                    if(dp[las][j][k][l])
                        for(int t=k;t<=n-j;t++)
                            if(l*c[t-1][k-1]<=K)
                                add(dp[now][j+t][t-k][l*c[t-1][k-1]],dp[las][j][k][l]);
        int tmp=0;
        for(int j=2;j<=n;j++)
            for(int l=1;l<=K;l++)add(tmp,dp[now][j][0][l]);
        add(ans,(ll)tmp*(m-i+1)%mod);
    }
    cout<<ans<<'\n';
    return 0;
}

思路&代码借鉴此博客

深深地感到自己的弱小。