P8340 题解

· · 题解

不需要每次减半的做法。（？）

首先充要条件显然是 1+\sum_{i=1}^ja_i\geq a_{j+1}，我们可以假定一定选 n+1。

考虑容斥，选定一些 1+\sum_{i=1}^ja_i<a_{j+1}。

注意到 a_1<a_2<\dots<a_k 的和在 k=O(\sqrt n) 的时候就超过了 n。因此我们会发现选定的 j 一定有 j\leq O(\sqrt n)。

先考虑计算 a_1<a_2<\dots<a_k 且 sum=n'\leq n 的方案数。转化为每次将所有正数减一。考虑 dp_{i,j} 表示目前考虑的 sum=i 且 a_{k-j+1}\sim a_k 还不为 0 的方案数，容易转移。考虑到 k\leq O(\sqrt{n'})，我们可以 O(n\sqrt n) 对于所有 (k,n') 求出答案。

接下来考虑带上选定我们该如何设计 dp 状态。我们希望在每次选定之前都有 dp 某一维等于真实的 sum。沿用上面的 dp_{i,j} 即可正确转移：对于 dp_{i,j=1}，i 就是实际上的 sum，考虑选定的转移，枚举本次选定到下一次选定之间有多少 a_x，先“预付”每个这一段之间的 a_x\gets i，然后继续用同一个 dp 转移。也就是：dp_{i,1}\to dp_{i+(i+2)\times k,k}。（当然由于是容斥系数显然应该是 -1。）

还有最后一个问题：最后一个选定的怎么办。我们发现在最后一个选定之后的部分我们可以直接忽略，也就是贡献是 2^{n-sum-1}。因此在每个 dp_{i,1} 处将 -2^{n-i-1}dp_{i,1} 计入答案即可。特判一下 i=0 以及啥都不选。总复杂度 O(n\sqrt n)。

由于他不让开 O(n\sqrt n) 空间，我们得滚动数组。实现上讲，我们将 dp_{i,1} 额外存下来，从 i+(i+2)\times k 处反过来枚举 k 转移。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
int mod;
inline void add(int &i,int j){
    i+=j;
    if(i>=mod) i-=mod;
}
inline int addv(int i,int j){
    i+=j;
    if(i>=mod) i-=mod;
    return i;
}
const int B=1000;
int dp[1005][1005];
int del[1005];
int f[1000005];
int pw2[1000005];
signed main(){
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
//  ios::sync_with_stdio(false);
//  cin.tie(0),cout.tie(0);
    int n; cin>>n>>mod;
    pw2[0]=1; for(int i=1;i<=1000000;i++) pw2[i]=addv(pw2[i-1],pw2[i-1]);
    for(int i=1;i<=B;i+=2) dp[0][i]=1;
    f[0]=1;
    int ans=pw2[n-1];
    for(int i=1;i<n;i++){
        int p=i%B;
        memset(dp[p],0,sizeof(dp[p]));
        del[0]=p;
        for(int j=1;j<=B;j++){
            int x=i-j*2;
            if(x%(j+1)==0) add(dp[p][j],mod-f[x/(j+1)]);
        }
        for(int j=1;j<=B;j++) del[j]=(del[j-1]==0)?999:del[j-1]-1;
        for(int j=1;j<=B;j++) add(dp[p][j],addv(dp[del[j]][j],dp[del[j]][j+1]));
        f[i]=dp[p][1];//jump
        add(ans,mod-1ll*dp[p][1]*pw2[n-i-1]%mod);
    }
    cout<<ans;
    return 0;
}