Wannafly挑战赛18B 随机数

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 imes 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}_{ ext{n个}}f_0+B)+B)cdots +B)+B=B(1+A+A^2cdots A^{n-2}+A^{n-1}))

等比数列求和即可

最后(A^n)的(n)可以降幂变成(A^{n ext{ 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
",(A*B%mod*n%mod+B)%mod);
	else printf("%lld
",B*(mod+pow(A,n)-1)%mod*inv(A-1)%mod);
	return 0;
}