Wannafly挑战赛18B 随机数

设\(f_i\)表示生成\(i\)个数有奇数个1的概率。

那么显而易见的递推式：\(f_i=p(1-f_{i-1})+(1-p)f_{i-1}=(1-2p)f_{i-1}+p\)

简化一下，设\(A=1-2p,B=p\)则\(f_i=A\times f_{i-1}+B\)

大力拆。。。\(f_n=Af_{n-1}+B=A(Af_{n-2}+B)+B=A(A(Af_{n-3}+B)+B)+B...\)

最后\(f_n=\underbrace{(A(A(A(\cdots(A}_{\text{n个}}f_0+B)+B)\cdots +B)+B=B(1+A+A^2\cdots A^{n-2}+A^{n-1})\)

等比数列求和即可

最后\(A^n\)的\(n\)可以降幂变成\(A^{n\text{ mod }(P-1)}\)

注意\(A=1\)的特判

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

#define mod 1000000007

il int gi(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

ll a,n,len,A,B,s;

char N[1000010];

il ll pow(ll x,ll y){

	ll ret=1;

	while(y){

		if(y&1)ret=ret*x%mod;

		x=x*x%mod;y>>=1;

	}

	return ret;

}

il ll inv(ll x){

	ll ret=1,y=mod-2;

	while(y){

		if(y&1)ret=ret*x%mod;

		x=x*x%mod;y>>=1;

	}

	return ret;

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("129b.in","r",stdin);

	freopen("129b.out","w",stdout);

#endif

	a=gi();

	scanf("%s",N+1);len=strlen(N+1);

	if(a==5000)s=mod;

	else s=mod-1;

	for(int i=1;i<=len;++i)n=(n*10+N[i]-'0')%s;

	B=a*inv(10000)%mod,A=(mod+mod+1-B-B)%mod;

	if(a==5000)printf("%lld\n",(A*B%mod*n%mod+B)%mod);

	else printf("%lld\n",B*(mod+pow(A,n)-1)%mod*inv(A-1)%mod);

	return 0;

}

巴特西

Wannafly挑战赛18B 随机数

Wannafly挑战赛18B 随机数

最新文章

热门文章