CF1561D Up the Strip (整除分块 dp 因子)

简介: CF1561D Up the Strip (整除分块 dp 因子)

Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))

D1. Up the Strip (simplified version)

D2. Up the Strip

题意:

给出一个数n,每次有两种操作,设x为当前数字


选择1 < = y < = x − 1 , x = x − y

选择2 < = z < = x , x = x /2(向下取整)

问从n nn变为1 11的方案数。

e a s y   v e r s i o n 中n < = 2 e 5

h a r d   v e r s i o n 中n < = 4 e 6

思路:

假设d p [ i ]表示从i变到1的方案数,那么d p [ i ] = ∑ j = 1 i − 1 d p [ j ] + ∑ k = 2 i d p [ i k ]

前一项表示通过减法到达j,后一项表示通过除法到达k。

这样的复杂度是O ( n 2 )的,考虑能够怎么优化。

∑ j = 1 i − 1 d p [ j ]可以用前缀和优化,每次加上s u m i − 1 就行。

后面一项,由于每次都是向下取整,真正的除数只有i个,可以用整除分块来做,每次维护因子能够影响到的区间。时间复杂度O ( n n )

学习链接

for(int l=2,r;l<=i;l=r+1){
      r=i/(i/l);
      dp[i]=(dp[i]+(r-l+1)*dp[i/l]%mod)%mod;
}

这个复杂度过d 2显然不大行,考虑进一步的优化。

看看是否能从后继状态转移过来,比如当枚举到x时,除数为2,那么2 x , 2 x + 1就可以通过除2到达x。

进一步的扩展,对于x的每个除数y,都能够通过[ z y , z y + y − 1 ]中的数除y到达x。

可以枚举倍数,并且维护后缀和。时间复杂度O ( n l o g n )

for(int j=2;j*i<=n;j++){//(i*j)/j=i,所以i*j可以转移到i
  int r=min(n,(ll)i*j+j-1);//右边界
  dp[i]=(dp[i]+sum[i*j]-sum[r+1]+mod)%mod;//后缀和
}

代码:

D 1 D1D1

const int maxn=2e5+10;
ll n,dp[maxn],mod,sum[maxn];
int main(){
  n=read,mod=read;
  dp[1]=1;dp[2]=2;
  sum[1]=1,sum[2]=3;
  rep(i,3,n){
    dp[i]=(dp[i]+sum[i-1])%mod;
    for(int l=2,r;l<=i;l=r+1){
      r=i/(i/l);
      dp[i]=(dp[i]+(r-l+1)*dp[i/l]%mod)%mod;
      //cout<<l<<" "<<r<<" "<<dp[i]<<endl;
    }
    sum[i]=(sum[i-1]+dp[i])%mod;
  }
  /*rep(i,1,n){
    cout<<i<<" "<<dp[i]<<endl;
  }*/
  printf("%lld\n",dp[n]);
  return 0;
}

D2

const int maxn=4e6+10;
ll n,dp[maxn],mod,sum[maxn];
int main(){
  n=read,mod=read;
  dp[n]=sum[n]=1;
  per(i,n-1,1){
    dp[i]=sum[i+1];
    //sum[i]=(sum[i+1]+dp[i])%mod;
    for(int j=2;j*i<=n;j++){
      int r=min(n,(ll)i*j+j-1);
      dp[i]=(dp[i]+sum[i*j]-sum[r+1]+mod)%mod;
    }
    sum[i]=(sum[i+1]+dp[i])%mod;
  }
  write(dp[1]);
  return 0;
}

参考

昨晚比赛结束了看群里的讨论,两个题本质是d p dpdp的转移方式

20200401134307494.png

好有道理~

目录
相关文章
|
9月前
【每日一题Day289】LC1749任意子数组和的绝对值的最大值 | dp
【每日一题Day289】LC1749任意子数组和的绝对值的最大值 | dp
58 0
|
算法
求最大连续子段和 的 dp算法
对于这样的问题,我们可以直接用暴力,一个双重循环,虽说可以,但也没有更高明的方法? 我们再分析这个问题,如果我们知道了某个数前面一段数的和,我们就该考虑把这个数加入到前一段,还是重新开始一段。这个地方很重要,如果前一段的和小于0,我们重新建一段,反之加到前一段。这样我们就可以把n个数分成几段了,且每一段都求出了他们的和,然后再循环一次求出最大的一个和,我们就得到想要的结果了,也可以在分段的时候直接求结果。
60 0
|
9月前
|
算法
算法系列--两个数组的dp问题(2)(下)
算法系列--两个数组的dp问题(2)(下)
49 0
|
9月前
|
算法
算法系列--两个数组的dp问题(1)(上)
算法系列--两个数组的dp问题(1)
47 0
|
9月前
|
算法
算法系列--两个数组的dp问题(2)(上)
算法系列--两个数组的dp问题(2)
45 0
|
9月前
|
算法 计算机视觉
算法系列--两个数组的dp问题(1)(下)
算法系列--两个数组的dp问题(1)
64 0
|
机器学习/深度学习
CF189A Cut Ribbon(dp一维思想,完全背包最详细解析)
CF189A Cut Ribbon(dp一维思想,完全背包最详细解析)
101 0
|
人工智能 算法
A. Average Height(找相邻的数除2产生整数更多的排列)(codeforces715)
A. Average Height(找相邻的数除2产生整数更多的排列)(codeforces715)
45 0
cf 327A (前缀和优化dp)
cf 327A (前缀和优化dp)
78 0

热门文章

最新文章