专栏文章

0608

CCap1taL
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip4a8u1
此快照首次捕获于
2025/12/03 05:55
3 个月前
此快照最后确认于
2025/12/03 05:55
3 个月前
查看原文

AT_abc409_g

卷积的部分没啥好说的，主要是前面推式子部分
朴素计算期望，需要做一个 DP gi,jg_{i,j} 表示从后往前考虑到 ii，选了 jj 个的概率，进行转移。这个 jj 是省不掉的，因为系数与其相关，似乎也提不出来
最后我们需要的只是 Gi=∑jjgi,jG_i=\sum_jjg_{i,j}，即枚举出现次数后累加期望
但这个期望是可以直接计算的！发现 gi,jg_{i,j} 的系数关于 jj 是线性的，期望可以穿透线性的函数
Gi=E[前i个选的数量]=E[前i−1个选的数量+第i个选没选]=E[前i−1个选的数量]+E[第i个选没选]=Gi−1+E[f(i,前i个选的数量)]G_i=E[前 i 个选的数量]=E[前i-1个选的数量+第i个选没选]\\ =E[前i-1个选的数量]+E[第i个选没选]\\ =G_{i-1}+E[f(i,前i个选的数量)]\\
然后 f(i,X)f(i,X) 确为线性，于是可以把这个期望拆进去，直接转移 GiG_i 得到期望
后面还有个部分，计算了这样的式子
∑i=0n−kFi+kGi\sum_{i=0}^{n-k}F_{i+k}G_i
这样滑动的积的形式。事实上，直接翻转 FF，即令 Fi=Fn−iF_i=F_{n-i}，可以变成
∑i=0n−kFn−k−iGi\sum_{i=0}^{n-k}F_{n-k-i}G_i
变成卷积的形式。
因为没怎么推过卷积式子所以卡了有一会，问了GPT才知道是卷积，记录一下
用了 ATCoder Library 的 convolution 和 modint
CPP
#include <atcoder/modint>
#include <atcoder/convolution>

int n,p;

int ans[MAXN];

int fac[MAXN];
int ifac[MAXN];
int inv[MAXN];

void solve(bool SPE){
	n=RIN,p=RIN;
	
	if(p==100){
		foru(i,1,n){
			cout<<1<<endl;
		}
		return ;
	}
	
	p=mul(p,qpow(100,mod-2));
	
	int q=rmv(1,p);
	int _q=qpow(q,mod-2);
	 
	foru(i,1,n){
		inv[i]=qpow(i,mod-2);
	}
	fac[0]=1;
	foru(i,1,n){
		fac[i]=mul(fac[i-1],i);
	}
	ifac[n]=qpow(fac[n],mod-2);
	ford(i,n-1,0){
		ifac[i]=mul(ifac[i+1],i+1);
	}
	// cout<<mul(fac[3],ifac[2],ifac[1])<<endl;
	
	static int G[MAXN];
	G[n]=1;
	ford(i,n-1,1){
		G[i]=add(G[i+1],mul(q,G[i+1],inv[i]));
	}
	
	
	ans[1]=G[1];
	
	foru(i,2,n){
		mll(G[i],fac[i-2],qpow(q,i));
	}
	
	static int H[MAXN];
	foru(i,2,n){
		H[i]=mul(ifac[i-2],qpow(p,i-1),qpow(_q,i));
	}
	
	// cout<<g[n][0]<<endl;
	
	typedef atcoder::static_modint<998244353> mint;
	// static int F[MAXN];
	vector<mint> ff(n+1,0);
	vector<mint> ii(n+1,0);
	
	foru(i,0,n){
		// cout<<G[n-i]<<endl;
		ff[i]=G[n-i];
		ii[i]=ifac[i];
		// F[i]=G[n-i];
	}
	// return ;
	
	// static int CV[MAXN];
// 	
	// foru(k,0,n){
		// foru(i,0,k){
			// mdd(CV[k],mul(F[i],ifac[k-i]));
		// }
	// }
	vector<mint> CV=atcoder::convolution(ff,ii);
	
	foru(k,1,n){
		int x=CV[n-k].val();
		ans[k]+=mul(x,H[k]);
	}
	
	
	foru(i,1,n){
		printf("%d\n",ans[i]);
	}
	
	return ;
}

NTT

半学半背板地把 NTT 学了
FFT 还是记得的，核心是单位根具有性质，因此后半部分的点值可以用前半部分的递归结果计算。迭代版就是把二进制位翻转后重排数组，使得可以从底向上计算
换到模意义下就变成了原根。998244353=119×223+1998244353=119\times2^{23}+1，所以可以做不超过 2232^{23} 。应付一些简单的卷积足够了。它的原根是 33。
CPP
namespace NTT{
	constexpr int g=3;
	constexpr int _g=qpow(3,mod-2);
	typedef vector<int> v;
	v r;
	void NTT(v& a,bool inv){
		int n=a.size();
		foru(i,0,n-1)	if(i<r[i])	swap(a[i],a[r[i]]);
		for(int len=2;len<=n;len<<=1){
			int W=qpow(inv?_g:g,(mod-1)/len);
			for(int i=0;i<n;i+=len){
				for(int j=0,w=1;j*2<len;j++,mll(w,W)){
					int x=a[i+j],y=mul(a[i+j+len/2],w);
					a[i+j]=add(x,y);
					a[i+j+len/2]=rmv(x,y);
				}
			}
		}
		if(inv){
			int _n=qpow(n,mod-2);
			foru(i,0,n-1)	mll(a[i],_n);
		}
	}
	v convolution(const v& x,const v& y){
		v A=x,B=y;
		int N=1,L=0,n=x.size(),m=y.size();
		while(N<n+m-1)	N<<=1,L++;
		A.resize(N,0),B.resize(N,0),r.resize(N,0);
		foru(i,0,N-1)	r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
		NTT(A,0);
		NTT(B,0);
		v ret(N,0);
		foru(i,0,N-1)	ret[i]=mul(A[i],B[i]);
		NTT(ret,1);
		return ret;
	} 
}
还是很好记的
会写错的几个地方
  • 检查有没有协会曾 constexpr int _g=3
  • 检查 NTT 时有没有写成 len<n
  • 检查 NTT 时有没有写成 i<=n
  • 检查 NTT 时有没有写成 j*2<=len
  • 检查 w 的计算和处理
  • 检查有没有忘了在做逆变换时乘 nn 的逆元
  • 检查计算二进制翻转时有没有不小心打成 (r[i>>1]>>1)|((i&1)<<1)。应为 (r[i>>1]>>1)|((i&1)<<(L-1))
  • 检查 NTT 的参数列表是否为 vector<int>&

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...