[AGC049D] Convex Sequence

Marsrayd / 2023-05-19 / 原文

给定整数 \(n\) 和 \(m\)，问有多少个长为 \(n\) 的非负整数数列 \(A\)，满足以下条件：

\(A_1+A_2+\ldots+A_n = m\)

对任意 \(i(2 \leq i \leq N-1)\) ，都有 \(2A_i \leq A_{i-1} + A_{i+1}\)

答案对 \(10^9+7\) 取模。

\(\texttt{data range}\)：\(n,m\le 100000\)。

通过题目名称 "Convex" 和题设，可以显然的看出题目的限制就是数列数值具有不严格凸性，那么可以很容易地想到一阶差分递增，二阶差分为正数。

秉承 “条件能用则用” 原则，如果使用差分将凸性简化，就会导致 “非负” 失去它的作用，于是可以考虑将差分投影到原序列。

没有参考点很麻烦，考虑枚举最小值所在的地方，以参考点为原点往两边差分，那么从参考点开始往两边都应该递增，其构成可刻画为：

全局 \(+1\)（一阶差分原点 \(+ 1\)）。
前缀（不能越过最小值）加公差为 \(-1\) 末项为 \(1\) 的等差数列（一阶差分前缀加）。
后缀（不能越过最小值）加公差为 \(1\) 首项为 \(1\) 的等差数列（一阶差分后缀加）。

并且通过差分数组角度，容易证明构成方法不同，形成的数组一定不同，于是可以使用背包计数求解，物品只有 \(\sqrt(n)\) 种，时间复杂度 \(\mathcal O(m\log m)\)。

参考代码

#include<bits/stdc++.h>
#define int long long
#define F(i,j,k) for(i=(j);i<=(k);++i)
#define D(i,j,k) for(i=(j);i>=(k);--i)
using namespace std;
#define TIME 1e3*clock()/CLOCKS_PER_SEC
bool OP; double Mbe=TIME;
constexpr int N=200003,mod=1000000007;
char I[22000038],*J=I;
inline int read()
{
	int x=0,y=1;
	while(*J<48||*J>57) if(*J++=='-') y=-1;
	while(*J>=48&&*J<=57) x=(x<<1)+(x<<3)+(*J++^48);
	return x*y;
} 
int n,m,ans;
inline void Inc(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Dec(int &x,int y){x-=y-mod;if(x>=mod) x-=mod;}
inline void inc(int *f,int v)
{
	if(!v) return;
	int i;
	F(i,v,m) Inc(f[i],f[i-v]);
}
inline void dec(int *f,int v)
{
	if(!v) return;
	int i;
	D(i,m,v) Dec(f[i],f[i-v]);
}
int f[N],v[N];
bool ED;
signed main()
{
	//fprintf(stderr,"%.4lf MB\n",(&OP-&ED)/1048576.0);
	//#define Marsrayd //Look Out！
	#ifdef Marsrayd
		assert(freopen("data.in","r",stdin));
		assert(freopen("zj.out","w",stdout));
	#endif
	assert(fread(I,1,22000038,stdin));
	int i,j,u;
	n=read(),m=read(),f[0]=1,inc(f,n);
	F(i,1,n)
	{
		v[i]=(1ll+i)*i/2;
		if(v[i]>m) break;
		inc(f,v[i]);
	}
	if(v[i]>m) v[i]=0;
	F(i,1,n)
	{
		if(i!=1&&!v[i-1]) break;
		inc(f,v[i-1]);
		dec(f,v[n-i+1]);
		Inc(ans,f[m-v[i-1]]);
	}
	printf("%lld",ans);
	//fprintf(stderr,"time = %.4lf ms\n",TIME-Mbe);
	return 0;
}

启发：