最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球新消息丨LOJ 3276 JOISC 2020 Day2 遗迹 题解 (计数DP)

来源：博客园


【资料图】

LOJ链接

UOJ链接

观察一下n次地震的过程，发现最后会有n个石柱高度为0，\(1,2\cdots n\)高度的石柱各有一个。假设现在已经确定了一种初始高度状态，我们来看看最后哪些石柱高度会大于0：

  • 首先，初始高度为n的两个石柱中，较右的会留下来，最后高度为n的石柱就是它
  • 接下来，最后高度为n-1的石柱是初始高度为n的两个石柱中较左的那个，以及初始高度为n-1的两个石柱中最右的那个
  • 以此类推\(\cdots\)

稍微推一下可以总结成以下过程：从大到小枚举每种初始高度，枚举到i时，把初始高度为i的两个石柱加入一个堆中，然后从堆中弹出最右的一个石柱，这个石柱就是最终高度为i的。最后堆中会剩下n个石柱，这些就是最后高度为0的。

知道了这个似乎还是不太好做。我们来看看在确定了初始状态后，能不能方便地确定每个石柱最后的高度。我们维护一个"剩余可用高度集合"S，初始\(S=\{1,2\cdots n\}\)。令第i个石柱的初始高度为\(h_i\)，我们从右到左遍历每个石柱i，并在S中找出\(\le h_i\)的最大的元素。如果这个元素不存在，那i号石柱最终的高度就是0；否则最终的高度就是这个元素的值，我们需要把这个元素从S中删除。根据上面总结的过程，这部分也很好理解。用最右边的石柱举个例子吧，由于它在所有的"取出最右"的过程中都能杀穿，所以它一定能抢到最终高度为\(h_{2n}\)的位置。

现在题目钦定了每个石柱最终高度是0(被删除)还是大于0(不被删除)，我们要求出满足这些条件的初始状态数。我们用dp来从右到左决定石柱的高度。一个合法的初始状态中每个高度都恰有2个石柱，为了便于dp，我们假设这两个石柱是不同的(相当于假设高度为i的石柱有红蓝两种，分配的时候任选一种不得重复)，最后把答案除以\(2^n\)即可。令\(dp_{i,j}\)表示处理完了最靠右的i个石柱，S中的前j个元素都已经被删掉，第j+1个元素没被删掉(如果存在的话)，且只决定了最右边的i个石柱中 钦定被删掉的那些 和 钦定没被删掉的那些中最终高度\(\le j\)的那些 的初始高度，其它石柱初始高度待定，此时的方案数。这句话包含的条件有点多，建议多看几遍。令最右的i个石柱中有\(cdel\)个钦定被删除，\(ckeep\)个钦定不被删除。(主动)转移有以下几种情况：

  • 当前石柱钦定被删掉。则它的初始高度必须\(\le j\)，否则它的最终高度就是j+1了。高度范围\([1,j]\)中一共有2j种石柱，钦定不被删的消耗了j种，钦定被删的消耗了\(cdel\)种，所以一共有\(2j-j-cdel\)种方案。因此，\(dp_{i+1,j}+=dp_{i,j}\cdot(j-cdel)\)。
  • 当前石柱钦定不被删掉，且选择初始高度后S被删除的连续前缀长度不变。那么我们就先不选它的初始高度，先待定，以后再选。\(dp_{i+1,j}+=dp_{i,j}\)。
  • 当前石柱钦定不被删掉，且选择初始高度后S被删除的连续前缀变长了。我们枚举k，表示S被删除的连续前缀长度从j变成了\(j+k\)。要从S中删除这多出来的k个元素，需要k个石柱，当前石柱占了一个(它刚好从S中删掉了j+1，选择它的初始高度的方案数是\(2k-(k-1)=k+1\))，我们还需要从\(ckeep-j\)个初始高度待定的中选出\(k-1\)个，由于这k-1个之间是有顺序的，所以方案数\(\binom{ckeep-j}{k-1}\cdot (k-1)!\)。还要乘上一个额外的方案数\(f_{k-1}\)，其中\(f_i\)表示在\(1-i\)的高度值，\(2i\)种不同石柱中选出i个，使得删掉的S中的元素刚好为\(1-i\)的方案数(注意只是选出，选出元素之间没有顺序)。综上，\(dp_{i+1,j+k}+=dp_{i,j}\cdot (k+1)\cdot \binom{ckeep-j}{k-1}\cdot (k-1)!\cdot f_{k-1}\)。

上面这部分的复杂度是\(O(n^3)\)的。

然后来求一下f。令\(dp2_{i,j}\)表示处理了最大的i种高度，选了j个石柱的方案数。为了保证合法，需要满足\(j总是\ge i\)(即j

总时间复杂度\(O(n^3)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL n,del[1210],dp2[610][610],f[610],dp[1210][610],fac[1210],inv[1210];int main(){  fileio();  freopen("temple.in","r",stdin);  freopen("temple.out","w",stdout);  fac[0]=1;repn(i,1205) fac[i]=fac[i-1]*i%MOD;  rep(i,1203) inv[i]=qpow(fac[i],MOD-2);  cin>>n;  rep(i,n+n+3) del[i]=1;  LL x;  rep(i,n)  {    scanf("%lld",&x);--x;    del[x]=0;  }  dp2[0][0]=1;  rep(i,n+1) for(int j=i;j<=min((LL)i+i,n);++j)  {    (dp2[i+1][j]+=dp2[i][j])%=MOD;    (dp2[i+1][j+1]+=dp2[i][j]*2)%=MOD;    (dp2[i+1][j+2]+=dp2[i][j])%=MOD;  }  rep(i,n+2) f[i]=dp2[i][i];  reverse(del,del+n+n);  dp[0][0]=1;  LL cdel=0,ckeep=0;  rep(i,n+n)  {    rep(j,ckeep+1) if(dp[i][j])    {      if(del[i])      {        if(j-cdel>=0)          (dp[i+1][j]+=dp[i][j]*(j-cdel))%=MOD;      }      else      {        (dp[i+1][j]+=dp[i][j])%=MOD;        repn(k,n-j)        {          LL lftkeep=ckeep-j;          if(k-1>lftkeep) break;          LL val=dp[i][j]*(k+1)%MOD;          if(k-1>0) (val*=fac[lftkeep]*inv[lftkeep-(k-1)]%MOD*f[k-1]%MOD)%=MOD;          (dp[i+1][j+k]+=val)%=MOD;        }      }    }    cdel+=del[i];ckeep+=(1-del[i]);  }  LL ans=dp[n+n][n];  (ans*=qpow(qpow(2,n),MOD-2))%=MOD;  cout<

关键词： 初始状态 时间复杂度 从右到左