[AGC049D] Convex Sequence 题解

题目链接

点击打开链接

题目解法

好题！！
考虑原题的限制相当于原序列下凸，即差分数组单调
考虑把原序列在第一个最小值处割成 \(2\) 半
因为原序列是凸的，所以非最小值的长度是 \(\sqrt {2m}\) 级别的
这可以让我们 \(dp\) 差分数组，即求满足 \(\sum\limits_{i=1}^{n'}ib_i=m'\) 的 \(b_i\) 个数，\(b\) 是单调不升的

单调的数组有一个比较套路的 \(dp\) 方法是：
当前有 \(i\) 个数，有 \(2\) 个操作是：加入一个 \(1\) 或 把每个数都 \(+1\)
这不难做到 \(O(m\sqrt m)\) 求出 \((n',m')\) 的满足条件的 \(b\) 序列个数

然后考虑合并两端的序列，考虑令 \(g_{i,j}\) 为右部有不超过 \(i\) 个数，和为 \(j\)，和包含了 \(n\times \min\) 的方案数
这不难用前缀和优化在 \(O(m\sqrt m)\) 的时间内求出

求答案是好求的，直接枚举左部的长度和 \(sum\) 即可

时间复杂度 \(O(m\sqrt m)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=100100,P=1e9+7;
int n,m,f[455][N],g[455][N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
    n=read(),m=read();
    int B=sqrt(m<<1)+5;
    f[0][0]=1;
    F(i,1,B) F(j,0,m){
        if(j>=i) f[i][j]=f[i-1][j-i];
        if(j>=i*(i+1)/2) inc(f[i][j],f[i][j-i*(i+1)/2]);
    }
    F(i,0,B) F(j,0,m){
        if(j>=n) g[i][j]=g[i][j-n];
        inc(g[i][j],f[i][j]);
    }
    F(i,1,B) F(j,0,m) inc(g[i][j],g[i-1][j]);
    int ans=0;
    F(i,0,min(n-1,B)) F(j,0,m) inc(ans,1ll*f[i][j]*g[min(n-i-1,B)][m-j]%P);
    printf("%d\n",ans);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}