【题解】牛客OI周赛1-提高组 C.序列 计数类DP+前缀和优化
链接:https://www.nowcoder.com/acm/contest/199/C
来源:牛客网
我们枚举不同数字的个数 。此时等价于这个问题,有 x 个箱子排成一排,任
意两个箱子之间距离不超过 k(超过 k 意味着可以把这个间距减小到 k,且是一个等价的序
列),第一个箱子和最后一个箱子的距离不超过 m 的方案数。设 表示放置了 个箱子,第 个箱子和最后一个箱子的距离为 的方案数。
注意要减去超过 的那些方案数。观察到这个状态转移方程可以利用前缀和优化至 。
将 个位置放入 种不同数字一共有 种不同的方法,其中 代表第二类斯特林数。
然后还要对 个数字进行大小定位,共有 种不同方法。
目标:
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=2e3+10;
int n,m,k;
ll fac[N],sum[N],f[N][N],s[N][N],ans;
int main()
{
scanf("%d%d%d",&n,&m,&k);
fac[0]=1;
for(int i=1;i<=n;i++)
{
s[i][1]=s[i][i]=1;fac[i]=(fac[i-1]*i)%mod;
for(int j=2;j<i;j++)
s[i][j]=(s[i-1][j-1]+j*s[i-1][j]%mod)%mod;
}
f[1][0]=1;
for(int i=2;i<=n;i++)
{
sum[0]=f[i-1][0];
for(int j=1;j<=m;j++)
sum[j]=(sum[j-1]+f[i-1][j])%mod;
for(int j=1;j<=m;j++)
f[i][j]=sum[j-1];
for(int j=k+1;j<=m;j++)
f[i][j]=(f[i][j]-sum[j-k-1]+mod)%mod;
}
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
ans=(ans+(s[n][i]*fac[i]%mod)*f[i][j]%mod)%mod;
printf("%lld\n",ans);
return 0;
}
总结
初拿到这道题毫无头绪。这题转化为一个放箱子的模型,通过一系列分析利用DP求解,很巧妙。