Codeforces 1158F - Density of subarrays（dp，神仙题）

人生中第一道 *3500（显然不是自己独立 AC 的），不过还是祭一下罢

神仙 D1F

首先考虑对于给定的序列 \(a_1,a_2,\dots,a_n\) 怎样求它的“密度”。假设其密度为 \(p\)，那么对于全部 \(c^p\) 个子序列一定存在恰好 \(c^{p-1}\) 个以 \(1,2,\dots,c\) 开头的子序列。考虑 \(a\) 数组中最短的前缀 \(a[1...k]\)，满足 \(a_1,a_2,\dots,a_k\) 中恰好包含了 \(1\sim c\) 中所有数，显然若不存在这样的前缀，则 \(p=0\)。根据 \(k\) 的定义可知 \(a_k\) 在 \(a[1...k]\) 中恰好出现了一次，我们考虑以 \(a_k\) 开头的 \(c^{p-1}\) 个子序列，显然对于它们在原序列中第一次出现的位置，设为 \(a_k,a_{d_1},a_{d_2},\dots,a_{d_{p-1}}\)，必定有 \(d_1>k\)，也就是说 \(a[k+1...n]\) 中必须包含全部长度为 \(p-1\) 的 \(c^{p-1}\) 个子序列。因此我们可以得到这样的引理：一个序列的密度，等于不断删除其一个包含 \(1\sim c\) 的前缀，最多的删除次数。（没想到 *1）

这样我们可以得到一个 \(dp\)，\(dp_{i,j}\) 表示以 \(i\) 开头的子序列中，密度至少为 \(j\) 的子序列有多少个（没想到 *2），显然 \(dp_{i,0}=2^{n-i}\)。考虑怎样转移，我们枚举这样以 \(i\) 开头的子序列的 \(k\)（\(k\) 的含义见上文）在原序列中所对应的位置 \(r\)，我们再记 \(f_{l,r}\) 为对于所有元素下标都 \(\in[l,r]\)，其中 \(a_l,a_r\) 必须被选择的序列中，有多少个满足 \(1\sim c\) 全部出现，并且 \(a_r\) 恰好出现一次。那么显然有 \(dp_{i,j}=\sum\limits_{r=i}^nf_{i,r}\sum\limits_{t=r+1}^{n+1}dp_{t,j-1}\)（没想到 *3），后面那个东西显然可以用前缀和优化，因此我们现在只需求出 \(f_{i,r}\) 即可。考虑 \(f_{l,r}\) 怎么求，显然若 \(a_l=a_r\)，那么 \(a_r\) 不可能在子序列中只出现一次，故 \(f_{l,r}=0\)；若 \(a_l\ne a_r\)，我们记 \(cnt_x\) 为 \(\sum\limits_{i=l+1}^{r-1}[a_i=x]\)，即 \(x\) 在 \((l,r)\) 中的出现次数，对于 \(a_r\)，显然只能在 \(a_r\) 中被选择一次，其他位置都不能被选择，方案数为 \(1\)；对于 \(a_l\)，显然它在 \((l,r)\) 中每一次出现都可以爱选不选，不选拉倒，反正 \(l\) 是必须要选的，不可能出现 \(a_l\) 在子序列中出现次数为 \(0\) 的情况，方案数 \(2^{cnt_{a_l}}\)，对于其余所有 \(x\ne a_l\land x\ne a_r\)，总共有 \(2^{cnt_{x}}\) 种选法，但由于出现次数不能为 \(0\)，故需减去 \(1\)，即 \(2^{cnt_x}-1\)，用乘法原理将它们乘起来即可。这个可以通过预处理 \(2^k-1\) 及其逆元实现 \(\mathcal O(1)\) 维护，即边扫描边维护。（没想到 *4）。处理完 \(dp_{i,j}\)，由于题目要求密度恰好为 \(k\) 的子序列个数，求个差分即可。

这样暴力复杂度是 \(n^3\) 的，不过有一个性质是这个密度不会超过 \(\lfloor\dfrac{n}{c}\rfloor\)（没想到 *5），因此你这个 \(j\) 只需处理到 \(\lfloor\dfrac{n}{c}\rfloor\)，复杂度 \(\dfrac{n^3}{c}\)。

然而当 \(c\) 特别小的时候该算法还是过不去，我们考虑另一个 \(c\) 越小越好的暴力并对其进行数据分治（BJOI 既视感）（没想到 *6）。记 \(DP_{i,j,S}\) 表示考虑到前 \(i\) 位，现在已经删了 \(j\) 个恰好包含 \(1\sim c\) 所有数的前缀，当前前缀中包含了 \(S\) 中所有数的方案数，这个转移就比较容易了罢，分当前元素选和当前元素不选两种情况转移，如果当前元素不选，那就直接转移到 \(DP_{i+1,j,S}\)，否则如果加上这个元素后 \(S\) 变成了 \(\{1,2,\dots,c\}\)，那咱就多分一组，转移到 \(DP_{i+1,j+1,\varnothing}\)，否则转移到 \(DP_{i+1,j,S\cup\{a_i\}}\)，时间复杂度 \(n2^c\dfrac{n}{c}\)。取 \(c=11\) 作为两个暴力的分界点复杂度最优。

然鹅这样还是会被卡常，这时候就要拿出我们的终极卡常武器了。这里有一个比较实用的卡常技巧，由于此题模数是 \(998244353\)，\(8\times 998244353\times 998244353\) 刚好在 long long 范围内，所以考虑开 long long 存 DP 数组，额外记录一个 \(cnt_{i,j}\) 表示 \(dp_{i,j}\) 距离上一次取模进行了几次加法，若 \(cnt_{i,j}\) 达到 \(8\) 就令 \(dp_{i,j}\leftarrow dp_{i,j}\bmod 998244353\)，这样取模常数就变成了原来的 \(\dfrac{1}{8}\)（没想到 *7）。当然如果你还是过不去（虽然我没遇到这样的情况），据楼下 ymx 神仙所说，可以在 CF 上使用 GNU C++17 (64) 这门语言，这样 long long 的常数能小很多。

最后注意特判 \(c=1\)。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=3e3;

const int MOD=998244353;

int n,c,a[MAXN+5];

int qpow(int x,int e=MOD-2){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

namespace sub1{//subtask solving c>log2(n)

	int f[MAXN+5][MAXN+5],sum[MAXN+5][MAXN+5];ll dp[MAXN+5][MAXN+5];

	int pw2_1[MAXN+5],inv2_1[MAXN+5],cnt[MAXN+5];

	void solve(){

		for(int i=1;i<=n;i++) pw2_1[i]=(2*pw2_1[i-1]+1)%MOD;inv2_1[0]=1;

		for(int i=1;i<=n;i++) inv2_1[i]=qpow(pw2_1[i]);

		for(int l=1;l<=n;l++){

			int mul=1,col=1;memset(cnt,0,sizeof(cnt));

			cnt[a[l]]++;

			for(int r=l+1;r<=n;r++){

				if(a[r]==a[l]) mul=2ll*mul%MOD;

				else{

					mul=1ll*mul*inv2_1[cnt[a[r]]]%MOD;

					cnt[a[r]]++;if(cnt[a[r]]==1) col++;

					mul=1ll*mul*pw2_1[cnt[a[r]]]%MOD;

				}

				if(col==c&&(a[l]^a[r])) f[l][r]=1ll*mul*inv2_1[cnt[a[r]]]%MOD;

			}

		}

		for(int i=n+1;i;i--) dp[i][0]=pw2_1[n-i]+1;

		for(int i=n+1;i;i--) sum[i][0]=(sum[i+1][0]+dp[i][0])%MOD;

		for(int j=1;j<=n/c;j++){

			int cnt=0;

			for(int i=n;i;i--) for(int k=i+1;k<=n;k++,cnt++){

				dp[i][j]+=1ll*f[i][k]*sum[k+1][j-1];

				if(cnt>>3) dp[i][j]%=MOD,cnt=0;

			}

			for(int i=n;i;i--) sum[i][j]=(sum[i+1][j]+dp[i][j]%MOD)%MOD;

		}

		for(int i=0;i<=n;i++){

			if(!i) printf("%d ",(sum[1][i]-sum[1][i+1]+MOD-1)%MOD);

			else printf("%d ",(sum[1][i]-sum[1][i+1]+MOD)%MOD);

		}

	}

}

namespace sub2{//subtask solving c<=log2(n)

	const int MAXP=1<<11;

	int dp[2][MAXN+5][MAXP+5];

	void solve(){

		int pre=0,cur=1;dp[0][0][0]=1;

		for(int i=1;i<=n;i++){

			for(int j=0;j<=n/c;j++)

				for(int k=0;k<(1<<c)-1;k++) dp[cur][j][k]=0;

			for(int j=0;j<=n/c;j++){

				for(int k=0;k<(1<<c)-1;k++){

					dp[cur][j][k]=(dp[cur][j][k]+dp[pre][j][k])%MOD;

					if((k|(1<<a[i]-1))==(1<<c)-1) dp[cur][j+1][0]=(dp[cur][j+1][0]+dp[pre][j][k])%MOD;

					else dp[cur][j][k|(1<<a[i]-1)]=(dp[cur][j][k|(1<<a[i]-1)]+dp[pre][j][k])%MOD;

				}

			} pre^=cur^=pre^=cur;

		}

		for(int j=0;j<=n;j++){

			int ret=0;

			for(int k=0;k<(1<<c)-1;k++) ret=(ret+dp[pre][j][k])%MOD;

			if(!j) ret=(ret-1+MOD)%MOD;printf("%d ",ret);

		}

	}

}

namespace sub3{//subtask solving c=1

	int fac[MAXN+5],ifac[MAXN+5];

	void init_fac(int n){

		fac[0]=ifac[0]=ifac[1]=1;

		for(int i=2;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;

		for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;

	}

	int binom(int x,int y){return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}

	void solve(){

		init_fac(n);printf("0 ");

		for(int i=1;i<=n;i++) printf("%d ",binom(n,i));

	}

}

int main(){

	scanf("%d%d",&n,&c);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	if(c>11) sub1::solve();

	else if(c>1) sub2::solve();

	else sub3::solve();

	return 0;

}

巴特西

Codeforces 1158F - Density of subarrays（dp，神仙题）

最新文章

热门文章