Fork me on GitHub

Codeforces301E

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$加一了)。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces301E

文章作者:wzf2000

发布时间:2017年12月23日 - 22:12

最后更新:2017年12月25日 - 11:12

原始链接:https://wzf2000.github.io/2017/12/23/Codeforces301E/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。