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

转移。

CPP

#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;
}

文章操作

相关推荐

评论

P8340 题解