AGC041D Problem Scores

Link
注意到题目给的要求等价于\(\forall i\in[2,n],\sum\limits_{j=1}^iA_i>\sum\limits_{j=0}^{i-2}A_{n-j}\)。
显然这个条件等价于\(\sum\limits_{j=1}^{\lceil\frac n2\rceil}A_i>\sum\limits_{j=0}^{\lceil\frac n2\rceil-2}A_{n-j}\)。
考虑\(a=\nabla A\)，上述条件等价于\(\sum\limits_{i=1}^nc_ia_i\)，其中\(c_i\)是个系数，随便推推就有了。
同时\(a\)还需满足\(a_1>0\wedge\forall i\in[2,n]a_i\ge0\wedge\sum\limits_{i=1}^na_i\le n\)。
即如果确定了\(a_2,\cdots,a_n\)，那么\(a_1\)有\(n-\sum\limits_{i=2}^n(c_i+1)a_i\)种取值。
dp一下就好了。

#include<cstdio>
int f[5007];
int min(int a,int b){return a<b? a:b;}
int main()
{
    int n,p,ans=0;
    scanf("%d%d",&n,&p),f[0]=1;
    for(int i=1;i<n;++i) for(int k=min(i,n-i+1),j=k;j<n;++j) (f[j]+=f[j-k])%=p;
    for(int i=0;i<n;++i) (ans+=1ll*(n-i)*f[i]%p)%=p;
    printf("%d",ans);
}