Warning: session_start(): open(/tmp/sess_033640bdfcb057e2c7971a7dacfb4579, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛68

这是本文档旧的修订版!


牛客练习赛68

D 牛牛的粉丝

题意

一个长度为 $n$ 的环,初始位置 $i$ 有 $x_i$ 个人。

接下来每步,每个人有 $\frac as$ 概率向前一步,$\frac bs$ 概率向后一步,$\frac cs$ 概率不动,其中 $s=a+b+c$。

问 $k$ 次后每个位置的人数期望。

题解 1

倍增 $\text{dp}$,${dp}(i,j)$ 表示初始只有位置 $0$ 有一人,则 $j$ 步后位置 $i$ 期望有几人。

不难得到状态转移方程,时间复杂度 $O(n^2\log k)$。

查看代码

查看代码

const int MAXN=505,mod=998244353;
int n,dp[2][MAXN],x[MAXN],ans[MAXN],a,b,c,pos;
int quick_pow(int a,LL b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void Mul(){
	pos=!pos;
	mem(dp[pos],0);
	_for(i,0,n){
		_for(j,0,n)
		dp[pos][(i+j)%n]=(dp[pos][(i+j)%n]+1LL*dp[!pos][i]*dp[!pos][j])%mod;
	}
}
void Add(){
	pos=!pos;
	_for(i,0,n){
		dp[pos][i]=0;
		dp[pos][i]=(dp[pos][i]+1LL*a*dp[!pos][(i+n-1)%n])%mod;
		dp[pos][i]=(dp[pos][i]+1LL*b*dp[!pos][(i+1)%n])%mod;
		dp[pos][i]=(dp[pos][i]+1LL*c*dp[!pos][i%n])%mod;
	}
}
int main()
{
	n=read_int();
	LL k=read_LL(),Bit=0;
	a=read_int(),b=read_int(),c=read_int();
	_for(i,0,n)x[i]=read_int();
	while(k>=(1LL<<Bit))Bit++;
	Bit--;
	dp[0][0]=1;
	while(~Bit){
		if((k>>Bit)&1)
		Add();
		if(Bit)
		Mul();
		Bit--;
	}
	_for(i,0,n){
		_for(j,0,n)
		ans[(i+j)%n]=(ans[(i+j)%n]+1LL*x[i]*dp[pos][j])%mod;
	}
	int inv=quick_pow(quick_pow(a+b+c,mod-2),k);
	_for(i,0,n)space(1LL*ans[i]*inv%mod);
	return 0;
}
2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛68.1598669085.txt.gz · 最后更改: 2020/08/29 10:44 由 jxm2001