command_block 的博客

command_block 的博客

题解 P4707 【重返现世】

posted on 2019-06-29 19:59:41 | under 题解 |

广告:Min-Max容斥小记

好,我假设你们都会Min-Max容斥了。

题意:每秒按固定概率出现物品,求收集到$k$个物品的期望时间。

这道题还是很有难度的,这个黑牌不亏(或者是我的dp太菜了……)

分析:我们设集合$S$为某些物品的集合,物品的权值为第一次出现时间。

那么$E(min(S))$就是这些物品中有其中一个出现的期望时间。

每一次得到$S$中物品的概率是$\sum\limits_{i∈S}p_i$,那么期望时间就是$\dfrac{1}{\sum\limits_{i∈S}p_i}$。

我们能求$E(min(S))$了,我们再想想,$E(Kthmin(U))$($U$是全集)不就相当于期望耗时吗?

我们令下文的$k=n-k+1$,求的就是$E(Kthmax(U))$了,同时在题目中看到,这里的$k<=11$。

套用扩展Min-Max容斥,我们就得到了式子:

$ANS=\sum\limits_{T∈S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}E(\min(T))$

但是这里的$n<=1000$不能直接$O(2^n)$统计……

我们观察发现,$m<=10000$,一道数数题居然限制值域?没准是复杂度和$m$有关的$dp$。

容易想到一个个加入物品,先观察求和的式子,变量只有$|T|,E(min(T))$两个。

$E(min(T))$和$\sum\limits_{i∈T}p_i$直接相关。

那就都设到状态里面呗,$f[i][j][k]$表示前$i$个物品,选了$j$个,$\sum\limits_{i∈T}p_i=k$的方案数。

到最后把方案数乘以对应权值,求个和就是答案了。

那么转移的话,可以考虑选或不选当前物品,选的话:

$f[i][j+1][k+p[i]]+=f[i-1][j][k];$

不选则原封不动$f[i][j][k]+=f[i-1][j][k];$

为了节省空间,可以把第一维滚掉。

复杂度$O(n^2m)$,可以拿到$70$分。

我们发现每个东西的贡献=($E(\min(T))*|T|$相关的一坨东西*方案数)。

那么我们可以直接把这个式子的一部分作为dp权值,就可以减少维数了,降过维之后,由于我们把未知量强行塞入了dp权值里面,很有可能是无法直接转移的,还要在状态上加维数。

这种技巧称作“权值包含状态”或者叫“换维打击”,把维数藏在权值里。

发现$k<=11$,那么这个新的维度很有可能就是$k$了。

到底是把$E(\min(T))$加入权值还是$(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$呢?

第一,前者是某个东西的倒数,相加将会变得十分恶心; 第二,只有后者与$k$相关。那么我们把后者加入状态,看看会发生什么……

设$f[i][j]$表示前$i$个物品,$\sum\limits_{i∈T}p_i=j$的$(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$和。

转移的话,还是可以考虑选或不选当前物品$x$:

不选$x$则原封不动$f[i][j]+=f[i-1][j];$

强制选的话,转移开始不对劲了:$f[i][j+p[i]]=f[i-1][j]?$

可以得到,$\sum(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$,加入了$x$之后就会变成$\sum(-1)^{|T|-k+1}\dbinom{|T|}{k-1}$

由于我们没有记录$|T|$,虽然$-1$很好办,但是这个组合数是很难处理的……

我们把这个组合数拆开,得到$\sum(-1)^{|T|-k+1}\dbinom{|T|}{k-1}=(-1)^{|T|-k+1}\left[\dbinom{|T|}{k-2}+\dbinom{|T|-1}{k-1}\right]$

再给它拆分开,得到$\sum(-1)^{|T|-k-1}\dbinom{|T|}{k-2}-\sum(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$

我一看,后面不就是$f[i-1][j]$吗?

前面的那部分$k$有些不对头,看来还要记录$k$这一维,我们猜对了!(顺便Orz出题人)

正确姿势:

设$f[i][j][k]$表示前$i$个物品,$\sum\limits_{i∈T}p_i=j$,而且$k$如所设的$(-1)^{|T|-k}\dbinom{|T|-1}{k-1}$和。

考虑选或不选当前物品$x$:

不选$x$则原封不动$f[i][j][k]+=f[i-1][j][k];$

强制选的话:继承上面的推导$f[i][j+p[i]][k]+=$

$\sum(-1)^{|T|-k-1}\dbinom{|T|}{k-2}+\sum(-1)^{|T|-k+1}\dbinom{|T|-1}{k-1}$

$=f[i-1][j][k-1]-f[i-1][j][k]$,皆大欢喜!

边界问题怎么办?$\dbinom{-1}{-1}=0$所以$f[0][0][0]=1;$即可。

为了省空间,仍然需要把第一维滚掉。

注意有$p_i=0$的情况。

Code:

#include<algorithm>
#include<cstdio>
#include<map>
#define mod 998244353
#define MaxM 10050
#define mod 998244353
using namespace std;
long long f[MaxM][15],ans;
int n,kk,m,p[MaxM];
long long powM(long long a,long long t)
{
  long long ans=1;
  while(t){
    if (t&1)ans=ans*a%mod;
    a=a*a%mod;
    t>>=1;
  }return ans;
}
int main()
{
  scanf("%d%d%d",&n,&kk,&m);kk=n-kk+1;
  for (int i=1;i<=n;i++)scanf("%d",&p[i]);
  f[0][0]=1;
  for (int i=1;i<=n;i++)
    if (p[i])
     for (int j=m-p[i];j>=0;j--)
      for (int k=kk;k;k--)
       f[j+p[i]][k]=(f[j+p[i]][k]+f[j][k-1]-f[j][k])%998244353;
  for (int j=1;j<=m;j++)
    ans=(ans+f[j][kk]*m%mod*powM(j,mod-2))%mod;
  printf("%lld",(ans+mod)%mod);
  return 0;
}