Codeforces301E 题解

wzf2000
2019年8月7日

Codeforces301E 题解

题意：

• 给出 $n,m,k$，询问有多少个长度为 $n$ 的数组 $b$ 满足以下要求：
  • $b[i] \leq b[i+1],1 \leq i < n$
  • $1 \leq b[1] \leq b[n] \leq m$
  • 将 $b$ 数组排列后有大于等于一种小于等于 $k$ 种排列 $a$ 满足以下要求：
    • $|a[i]-a[i+1]|=1(1 \leq i<n)$
    • $|a[n]-a[1]|=1$
    • $a[1]=min_{i=1}^{n}a[i]$
• $n,m,k \leq 100$

题解：

• 首先我们可以假设 $a[1]=1$，最后将答案乘上 $m-i+1$ 即可。
• 不妨破环成链，设 $a[n+1]=a[1]$。
• 设 $dp[i][j][k][l]$ 表示目前最大数为 $i$，已经有 $j$ 个数，有 $k$ 个空必须加数，满足的排列数已有 $l$ 种的方案数。
• 转移比较显然：
• 枚举 $i+1$ 的个数 $t$。
• $dp[i][j][k][l]->dp[i+1][j+t][t-k][l*C_{t-1}^{k-1}]$
• 注意，只有一个数显然是不可以的（因为我们开始已经让 $n$ 加一了）。

代码：

#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()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>K;
    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;
        }
    n++;
    int now=1,last=0;
    dp[now][0][1][1]=1;
    for (int i=0;i<=m;i++)
    {
        last=now,now^=1;
        if (i)
        {
            int tmp=0;
            for (int j=2;j<=n;j++)
                for (int l=1;l<=K;l++) add(tmp,dp[last][j][0][l]);
            add(Ans,(ll)tmp*(m-i+1)%mod);
        }
        if (i==m) break;
        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[last][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[last][j][k][l]);
    }
    cout<<Ans<<'\n';
    return 0;
}

 codeforces dp