agc041_d Problem Scores

agc041_d Problem Scores

https://atcoder.jp/contests/agc041/tasks/agc041_d

Tutorial

https://img.atcoder.jp/agc041/editorial.pdf

由于(A_i le A_{i+1}),所以设(x_i=A_i-A_{i-1}).特别的由于(A_1ge1),所以设$x_1=A_1 - 1 $

题目中的限制相当于对于(k in [1,n))有

[sum_{i=1}^{k+1} A_i > sum_{i=0}^{k-1} A_{n-i} ]

考虑如果 (k > lfloor dfrac n2 floor) 那么不等式两边消元后,会变为更小的(k)时的不等式.所以只需要对于(k le lfloor dfrac n2 floor)满足即可.

考虑(k<lfloor dfrac n2 floor)如果让(k)增加(1),那么左边会增加(A_{k+2}),右边会增加(A_{n-k}),且(A_{k+2}<A_{n-k}).所以实际上,我们只需要让(k=lfloor dfrac n2 floor)时的不等式成立即可

那么限制就可以表示为

• (x_1+x_2+cdots+x_n < N)
• (x_1 ge (x_2,x_3,cdots,x_n) cdot (0,1,2,cdots,2,1))

设 (x_2+cdots+x_n = a, (x_2,x_3,cdots,x_n) cdot (0,1,2,cdots,2,1)=b).那么(b le x_1 le N-a-1),也就是说贡献为(max(0,N-a-b)).

也就是说,其实只关心(a+b=(x_2,x_3,cdots,x_n) cdot (1,2,3,cdots,3,2)),用一个(O(n^2))的DP即可统计

Code

#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc() {
//	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x) {
	x=0; int f=1,ch=nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x*=f; 
}
typedef long long ll;
const int maxn=5000+5;
int mod;
int n;
int v[maxn];
int dp[maxn][maxn];
inline void upd(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
int main() {
	read(n),read(mod);
	v[2]=1;
	for(int i=3,j=n;i<=j;++i,--j) v[i]=v[j]=v[i-1]+1;
	dp[1][n]=1;
	for(int i=2;i<=n;++i) {
		for(int j=n;j>=0;--j) {
			upd(dp[i][j],dp[i-1][j]);
			if(j) upd(dp[i][max(0,j-v[i])],dp[i][j]);
		}
	}
	int an=0;
	for(int i=1;i<=n;++i) an=(an+(ll)i*dp[n][i])%mod;
	printf("%d
",an);
	return 0;
}