【考前冲刺Day1】黑红树

题面

题解转自zhber的这篇文章,本人对部分公式做了LaTex处理,如需转载请注明原作者

zhb原创出品，改编自高一暑假数学作业必修三那章最后一题

这是这套题唯一会比较防ak的题了

首先题目我写了一大堆，就是要把你搞晕的

题意是有两个人进行游戏，其中第一个人在每局中获胜的概率是\(\frac{p}{q}\)，如果有一个人比另一个人多赢两局，则游戏结束。现在给出T个询问，每个询问Q表示求游戏刚好在第Q轮结束的精确概率\(\frac{a}{b}\)的a%k和b%k。要求\(\frac{a}{b}\)是这个概率的最简分数。

解法是这样的：

我们把每两局压成一轮，只有三种可能：第一个人赢了，第二个人赢了，两人各赢一局。这样如果有人赢了游戏结束，平局时两人分数相同，相当于又开始一局

这样我们注意到一个显然的事实：游戏不可能在奇数局结束。因为由上面的推论+自己yy可知，要结束一定是在一轮以后，就是偶数局之后。这样不合法情况删掉一半了

第一个人一轮赢必须连赢两局，就是\((\frac{p}{q})^2\)，即\(\frac{p^2}{q^2}\)

第二个人一轮赢也是连赢两局，就是\((1-p/q)^2\)，通分完\(\frac{(p-q)^2}{q^2}\)
那么一局能结束的概率就是上面两个加起来，即\(\frac{p^2+(p-q)^2}{q^2}\)

一局不能结束的概率就是1-"上面那式子"

为简化条件，我们令一轮能结束的概率是A/B，一轮不能结束的概率是C/D。计算方法见上

那么对于有意义的询问，即偶数Q，令t=Q/2

那么比赛在第t轮即第Q局结束的充要条件是：在1到t-1轮两人都是平局，并且在第t轮比赛刚好结束

那么对于询问Q，\((\frac{C}{D})^{t-1} \times \frac{A}{B}\) 即是所求

到这里应该都还能理解吧

然后比较难搞的是取模。因为p、q是100级别，那么\(p^2\)、\(q^2\)是1w级别，就是说ABCD这些数都是10000级别

要求的分数分子是\(C^{t-1}\times A\)，分母是\(D^{t-1}\times B\)，还要进行约分完取模。我们可以直接预处理使得A和B、C和D分别互质，但是我们没法保证A和D、B和C分别互质。这样约分就有困难了。比如A分解质因数有2^十几次方吧，D只有2^1，那么在接下来的十几次操作中都要用D的2去约掉A的2。但是ABCD的数据规模还算小，所以我们暴力搞出前20轮的答案，然后这样一来改约的也就约干净了，然后每次分子只乘C分母只乘D，又没有约分，可以直接递推。

代码

#include<cstdio>
#define MX 10000     //ABCD的规模是10000
#define primeMX 1230     //10000以内1229个质数
#define LL long long
int prime[primeMX];
struct fenjie{
    int rep[primeMX];
}aa,bb,cc,dd;
int p,q,T,k,a,b,c,d;
int ss[primeMX];     //用于暴力，分解质因数之后直接加/减在上面，如果是正的表示分子的分解质因数有ss[i]个prime[i]，反之分母亦然
LL Q,last;
LL ansa[1000010],ansb[1000010];     //保存第i局结束的概率的分子分母
inline void shai()     //筛法
{
    bool mrk[10010]={0};
    int leng=0;
    for (int i=2;i<=MX;i++)
      if (!mrk[i])
      {
        for (int j=2*i;j<=MX;j+=i)mrk[j]=1;
        prime[++leng]=i;
      }
}
inline int gcd(int a,int b)     //gcd用于A和B、C和D先约分
{if (!b)return a;else return gcd(b,a%b);} 
inline void divide(fenjie &a,int b)     //分解质因数，用于前20轮暴力用
{
    for (int i=1;i<primeMX;i++)
      {
        if (b==1)break;
        while (b%prime[i]==0){b/=prime[i];a.rep[i]++;}
      }
}
inline LL read()     //快速读入，100w的询问不加肯定TLE
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    freopen("mynameisczy.in","r",stdin);
    freopen("mynameisczy.out","w",stdout);
    shai();
    p=read();q=read();T=read();k=read();
    if (p==1&&q==1||p==0&&q==0)ansa[2]=ansb[2]=1;  //如果必胜或必败，那一定在第2局就结束。其余概率都是0
    else
    {
        c=p*p+(q-p)*(q-p);
        b=q*q;
        a=b-c;
        d=b;        //这里我AB和CD的意义反过来了
        int div1=gcd(a,b);a/=div1;b/=div1;
        int div2=gcd(c,d);c/=div2;d/=div2;
        divide(aa,a);
        divide(bb,b);
        divide(cc,c);
        divide(dd,d);
        ansa[2]=c%k;ansb[2]=d%k;
        for (int i=1;i<primeMX;i++)
          ss[i]+=cc.rep[i]-dd.rep[i];
        for(int i=4;i<=40;i+=2)
        {
            long long sum1=1,sum2=1;
            for (int j=1;j<primeMX;j++)
              ss[j]+=aa.rep[j]-bb.rep[j];
            for (int j=1;j<primeMX;j++)
              if (ss[j]>0) for (int l=1;l<=ss[j];l++)sum1=(sum1*prime[j])%k;
              else if (ss[j]<0)for (int l=1;l<=-ss[j];l++)sum2=(sum2*prime[j])%k;
            ansa[i]=sum1;ansb[i]=sum2;
        }
        for (int i=42;i<=1000000;i+=2)
        {
            ansa[i]=(ansa[i-2]*a)%k;
            ansb[i]=(ansb[i-2]*b)%k;
        }
    }
    for(int i=1;i<=T;i++)
      {
        Q=read()-last;     //last是处理加密的问题
        last=ansa[Q];
        printf("%I64d %I64d\n",ansa[Q],ansb[Q]);
      }
    return 0;
}

#include<cstdio>

#define MX 10000 //ABCD的规模是10000

#define primeMX 1230 //10000以内1229个质数

#define LL long long

int prime[primeMX];

struct fenjie{

int rep[primeMX];

}aa,bb,cc,dd;

int p,q,T,k,a,b,c,d;

int ss[primeMX]; //用于暴力，分解质因数之后直接加/减在上面，如果是正的表示分子的分解质因数有ss[i]个prime[i]，反之分母亦然

LL Q,last;

LL ansa[1000010],ansb[1000010]; //保存第i局结束的概率的分子分母

inline void shai() //筛法

{

bool mrk[10010]={0};

int leng=0;

for (int i=2;i<=MX;i++)

if (!mrk[i])

{

for (int j=2*i;j<=MX;j+=i)mrk[j]=1;

prime[++leng]=i;

}

inline int gcd(int a,int b) //gcd用于A和B、C和D先约分

{if (!b)return a;else return gcd(b,a%b);}

inline void divide(fenjie &a,int b) //分解质因数，用于前20轮暴力用

{

for (int i=1;i<primeMX;i++)

{

if (b==1)break;

while (b%prime[i]==0){b/=prime[i];a.rep[i]++;}

}

inline LL read() //快速读入，100w的询问不加肯定TLE

{

LL x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int main()

{

freopen("mynameisczy.in","r",stdin);

freopen("mynameisczy.out","w",stdout);

shai();

p=read();q=read();T=read();k=read();

if (p==1&&q==1||p==0&&q==0)ansa[2]=ansb[2]=1; //如果必胜或必败，那一定在第2局就结束。其余概率都是0

else

{

c=p*p+(q-p)*(q-p);

b=q*q;

a=b-c;

d=b; //这里我AB和CD的意义反过来了

int div1=gcd(a,b);a/=div1;b/=div1;

int div2=gcd(c,d);c/=div2;d/=div2;

divide(aa,a);

divide(bb,b);

divide(cc,c);

divide(dd,d);

ansa[2]=c%k;ansb[2]=d%k;

for (int i=1;i<primeMX;i++)

ss[i]+=cc.rep[i]-dd.rep[i];

for(int i=4;i<=40;i+=2)

{

long long sum1=1,sum2=1;

for (int j=1;j<primeMX;j++)

ss[j]+=aa.rep[j]-bb.rep[j];

for (int j=1;j<primeMX;j++)

if (ss[j]>0) for (int l=1;l<=ss[j];l++)sum1=(sum1*prime[j])%k;

else if (ss[j]<0)for (int l=1;l<=-ss[j];l++)sum2=(sum2*prime[j])%k;

ansa[i]=sum1;ansb[i]=sum2;

}

for (int i=42;i<=1000000;i+=2)

{

ansa[i]=(ansa[i-2]*a)%k;

ansb[i]=(ansb[i-2]*b)%k;

}

for(int i=1;i<=T;i++)

{

Q=read()-last; //last是处理加密的问题

last=ansa[Q];

printf("%I64d %I64d\n",ansa[Q],ansb[Q]);

}

return 0;

}

Lxp_Mike

6年前

2018-11-03 21:50:56

我才是最强的！！！哈哈哈哈！！

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define MS(x,y) memset(x,y,sizeof(x))
#define N 1007
#define M 1007
#define gc getchar
#define pc putchar
#define LL long long
#define DB double
using namespace std;

LL T,q,p,K,Q,last;
int zup[M],zdown[M];
int B[M]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};

template <class _> inline void read(_ &x){
    char ch=gc();int fl=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')fl=-fl;ch=gc();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}
    x*=fl;
}

template <class _> inline void write(_ x){
    if(x<0) pc('-'),x=-x;
    if(x>10) write(x/10);
    pc(x%10+'0'); 
}

inline LL q_pow(LL x,LL y){
    LL res=1;res%=K;
    while(y){
        if(y&1) res=res*x%K;
        x=x*x%K;y>>=1;
    }
    return res;
}

inline void Div(LL x,LL y){
    for(LL i=2;i<=(LL)sqrt(x*1.0);++i){
        while(x%i==0) zup[i]+=y,x/=i;
    }
    if(x>1) zup[x]+=y;
}

inline void inDiv(LL x,LL y){
    for(LL i=2;i<=(LL)sqrt(x*1.0);++i){
        if(x%i==0){
            while(x%i==0) zdown[i]+=y,x/=i;
            if(zup[i]>=zdown[i]) zup[i]-=zdown[i],zdown[i]=0;
            else zdown[i]-=zup[i],zup[i]=0;
        }
    }
    if(x>1){
        zdown[x]+=y;
        if(zup[x]>=zdown[x]) zup[x]-=zdown[x],zdown[x]=0;
        else zdown[x]-=zup[x],zup[x]=0;
    }
}

inline void solve(){
    MS(zup,0),MS(zdown,0);
    LL up=1,down=1;
    Div(p*p+(q-p)*(q-p),1ll);
    Div(2*p*(q-p),(Q-2)/2);
    inDiv(q,Q);
    for(int j=1;j<=168;++j){
        int i=B[j];
        if(zup[i]>=1) up=(up*q_pow(i,zup[i]))%K;
    }
    for(int j=1;j<=168;++j){
        int i=B[j];
        if(zdown[i]>=1) down=(down*q_pow(i,zdown[i]))%K;
    }
    printf("%lld %lld\n",up,down);
    last=up;
}

int main(){
    read(p),read(q),read(T),read(K);
    while(T--){
        read(Q);
        Q-=last;
        if(Q%2||Q<=0) printf("0 0\n"),last=0;
        else solve();
    }
    return 0;
}

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <cmath>

#define MS(x,y) memset(x,y,sizeof(x))

#define N 1007

#define M 1007

#define gc getchar

#define pc putchar

#define LL long long

#define DB double

using namespace std;

LL T,q,p,K,Q,last;

int zup[M],zdown[M];

int B[M]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};

template <class _> inline void read(_ &x){

char ch=gc();int fl=1;x=0;

while(ch<'0'||ch>'9'){if(ch=='-')fl=-fl;ch=gc();}

while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}

x*=fl;

}

template <class _> inline void write(_ x){

if(x<0) pc('-'),x=-x;

if(x>10) write(x/10);

pc(x%10+'0');

}

inline LL q_pow(LL x,LL y){

LL res=1;res%=K;

while(y){

if(y&1) res=res*x%K;

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

}

return res;

}

inline void Div(LL x,LL y){

for(LL i=2;i<=(LL)sqrt(x*1.0);++i){

while(x%i==0) zup[i]+=y,x/=i;

}

if(x>1) zup[x]+=y;

}

inline void inDiv(LL x,LL y){

for(LL i=2;i<=(LL)sqrt(x*1.0);++i){

if(x%i==0){

while(x%i==0) zdown[i]+=y,x/=i;

if(zup[i]>=zdown[i]) zup[i]-=zdown[i],zdown[i]=0;

else zdown[i]-=zup[i],zup[i]=0;

}

if(x>1){

zdown[x]+=y;

if(zup[x]>=zdown[x]) zup[x]-=zdown[x],zdown[x]=0;

else zdown[x]-=zup[x],zup[x]=0;

}

inline void solve(){

MS(zup,0),MS(zdown,0);

LL up=1,down=1;

Div(p*p+(q-p)*(q-p),1ll);

Div(2*p*(q-p),(Q-2)/2);

inDiv(q,Q);

for(int j=1;j<=168;++j){

int i=B[j];

if(zup[i]>=1) up=(up*q_pow(i,zup[i]))%K;

}

for(int j=1;j<=168;++j){

int i=B[j];

if(zdown[i]>=1) down=(down*q_pow(i,zdown[i]))%K;

}

printf("%lld %lld\n",up,down);

last=up;

}

int main(){

read(p),read(q),read(T),read(K);

while(T--){

read(Q);

Q-=last;

if(Q%2||Q<=0) printf("0 0\n"),last=0;

else solve();

}

return 0;

}

Nietsne

6年前

2018-11-03 19:28:23

望早日 AC （我想引用

发送评论编辑评论

代码

评论

发送评论 编辑评论

发送评论编辑评论