题解：P11126 [ROIR 2024] 三等分的数组 (Day 2)

要想到上界

O(m^3)

的 dp 是简单的，重点在于复杂度分析。

记

dp_{i,j,k}

表示当前考虑到值为

i

的数字，当前数字剩余

j

个,上一个数字剩余

k

个的方案数。容易有转移：

dp_{i,j,k}\to dp_{i+1,a_{i+1}-x,j-x},3\mid k-x

滚动数组加枚举

j

，倒序枚举

x

即可做到一个上界

O(m^3)

的 dp。

由于数的总个数和

m

同阶，也许我们认为的上界会很松。

仔细分析一下，时间复杂度的贡献应该是

\sum_{i=1}^{m} cnt_{i-1}\times cnt_{i}

的，有

(a+b)^2\ge a^2+b^2\ge 2ab

，所以上界应是

\left(\sum_{i=0}^{m}cnt_i\right)^2=n^2

。

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
bool mbs;
#define ll long long
const int mod=1e9+7;
const int maxn=5e3+20;
ll sum[4],dp[2][maxn][maxn],n,a[maxn],m;
bool mbt;
int main(){
//	cerr<<(&mbs-&mbt)/1024.0/1024.0<<endl;
	n=read(),m=read();int x;
	for(int i=1;i<=n;i++) x=read(),a[x]++;
	dp[0][0][0]=1;
	for(int i=0;i<m;i++){
		int cur=(i&1);
		for(int j=0;j<=a[i];j++) for(int k=0;k<=a[i+1];k++) dp[cur^1][k][j]=0;
		for(int j=0;j<=a[i];j++){
			sum[0]=sum[1]=sum[2]=0;
			for(int x=(i==0?0:a[i-1]);x>=0;x--){
				sum[x%3]=(sum[x%3]+dp[cur][j][x])%mod;
				if(x<=min<ll>(j,a[i+1])) dp[cur^1][a[i+1]-x][j-x]=(dp[cur^1][a[i+1]-x][j-x]+sum[x%3])%mod;
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=a[m-1];i++) for(int j=0;j<=a[m];j++) if(i%3==0&&j%3==0) ans=(ans+dp[m&1][j][i])%mod;
	printf("%lld\n",ans); 
	return 0;
}
/*
3 1
1 1 1
*/

题解：P11126 [ROIR 2024] 三等分的数组 (Day 2)

文章操作

相关推荐

评论

题解：P11126 [ROIR 2024] 三等分的数组 (Day 2)