2024牛客暑期多校训练营4 - J. Zero （究极卡常）

\(O(N^2)\) AC。

输入后预处理 ? 数量的前缀和。

双层循环找所有的区间 \([l,r]\) 使区间内没有 \(0\)，找到以后直接用逆元+快速幂求 \(\frac{(r-l+1)^k}{2^{sum_{r}-sum_{l-1}}}\)，最后累加和。

因为数据过水，这样已经能 AC 了。

#include<cstdio>
using namespace std;

const int N=1e5+5,P=998244353;
int n,k;
char str[N];
int qsum[N]; //the number of '?' in str[1,i]

int quick_pow(long long x,int y)
{
	long long res=1;
	while(y)
	{
		if(y&1) res=res*x%P;
		x=x*x%P;
		y>>=1;
	}
	return (int)res;
}
inline int inv(int x)
{
	return quick_pow(x,P-2);
}

int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",str+1);
	for(int i=1;i<=n;i++)
		qsum[i]=qsum[i-1]+(str[i]=='?');
	long long ans=0;
	for(int l=1;l<=n;l++)
	{
		if(str[l]=='0') continue;
		for(int r=l;r<=n;r++)
		{
			if(str[r]=='0') break;
			int q=qsum[r]-qsum[l-1];
			ans=(ans+1ll*inv(quick_pow(2,q))*quick_pow(r-l+1,k))%P;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

然而，还没有到极限。

预处理出所有的 \(2^i \bmod 998244353, i \in [0,n]\) 和 \(i^k \bmod 998244353, i \in [0,n]\)，这样过程中就可以不用重复计算。

但还不够，inv(quick_pow(2,q)) 同样可以预处理，所以在前面同时预处理 \((2^i)^{-1} \bmod 998244353\)，这样过程中也不用计算逆元了。

#include<cstdio>
using namespace std;

const int N=1e5+5,P=998244353;
int n,k;
char str[N];
int qsum[N]; //the number of '?' in str[1,i]
int binpow[N],powk[N],invbinpow[N];

int quick_pow(long long x,int y)
{
	long long res=1;
	while(y)
	{
		if(y&1) res=res*x%P;
		x=x*x%P;
		y>>=1;
	}
	return (int)res;
}
inline int inv(int x)
{
	return quick_pow(x,P-2);
}

int main()
{
//	freopen("zero.in","r",stdin);
//	freopen("zero.out","w",stdout);
	
	scanf("%d%d",&n,&k);
	scanf("%s",str+1);
	binpow[0]=1;
	invbinpow[0]=inv(binpow[0]);
	for(int i=1;i<=n;i++)
	{
		qsum[i]=qsum[i-1]+(str[i]=='?');
		binpow[i]=binpow[i-1]<<1;
		if(binpow[i]>=P) binpow[i]-=P;
		invbinpow[i]=inv(binpow[i]);
		powk[i]=quick_pow(i,k);
	}
	long long ans=0;
	for(int l=1;l<=n;l++)
	{
		if(str[l]=='0') continue;
		for(int r=l;r<=n;r++)
		{
			if(str[r]=='0') break;
			int q=qsum[r]-qsum[l-1];
			ans=(ans+1ll*invbinpow[q]*powk[r-l+1])%P;
		}
	}
	printf("%lld\n",ans);
	return 0;
}