BZOJ5340 & 洛谷4564 & LOJ2552：[CTSC2018]假面—

（这送分题我写不出来……我退役吧）

也懒得写题解了，看https://kelin.blog.luogu.org/solution-p4564吧。

什么你说op=1的你没听懂，那你可能和我一样了（握手（大雾。

那么遵从原题解的命名，f[u][i]表示除u以外有i个人活着的概率，g[i]为i个人活着的概率，p[u]表示u活着的概率。

（其实正确的思路应该先想到g数组如何求，然后发现g数组的信息无法落到每个具体人的头上，所以需要f数组。）

则可以发现，g的范围比f大（包括了u活着的可能性），于是需要扣除u活着时候有i个人活着的概率。

所以答案就是g[i]-p[u]*f[u][i-1]了……等等我怎么样例都过不去emmm

其实！这个式子蕴含了一个信息就是保证了u是死的，而实际上我们要求的是不知道u的死活的概率，于是除以（1-p[u]）就是答案了。

（然而这个思路可能考场上很难想吧……大部分人应该都是靠推推出来的这个式子，只有我啥也不会……）

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

const int p=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

inline void write(int x){

    if(x>)write(x/);

    putchar(x%+'');

}

int qpow(int k,int n){

    int res=;

    while(n){

        if(n&)res=(ll)res*k%p;

        k=(ll)k*k%p;n>>=;

    }

    return res;

}

int n,q,f[N][],g[N],h[N],s[N],inv[N];

inline int add(ll x,int y){

    x+=y;if(x>=p)x-=p;return x;

}

inline int sub(int x,int y){

    x-=y;if(x<)x+=p;return x;

}

int main(){

    n=read();

    for(int i=;i<=n;i++)f[i][read()]=;

    inv[]=;

    for(int i=;i<N;i++)inv[i]=(ll)(p-p/i)*inv[p%i]%p;

    q=read();

    while(q--){

        int op=read();

        if(!op){

            int id=read(),u=read(),v=read();

            int P=(ll)u*qpow(v,p-)%p;

            f[id][]=(f[id][]+(ll)P*f[id][]%p)%p;

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

                f[id][i]=add((ll)sub(,P)*f[id][i]%p,(ll)P*f[id][i+]%p);

        }else{

            int k=read();

            for(int i=;i<=k;i++)s[i]=sub(,f[read()][]),h[i]=;

            h[]=;

            for(int i=;i<=k;i++)

                for(int j=i;j>=;j--)

                    if(!j)h[j]=(ll)sub(,s[i])*h[j]%p;

                    else h[j]=add((ll)s[i]*h[j-]%p,(ll)(p+-s[i])*h[j]%p);

            for(int i=;i<=k;i++){

                if(!s[i]){putchar('');putchar(' ');continue;}

                if(s[i]==)

                    for(int j=;j<=k-;j++)g[j]=h[j+];

                else{

                    int Inv=qpow(sub(,s[i]),p-);g[]=(ll)h[]*Inv%p;

                    for(int j=;j<=k-;j++){

                        g[j]=(ll)sub(h[j],(ll)g[j-]*s[i]%p)*Inv%p;

                    }

                }

                int ans=;

                for(int j=;j<=k-;j++)ans=add(ans,(ll)g[j]*inv[j+]%p);

                write((ll)ans*s[i]%p);putchar(' ');

            }

            putchar('\n');

        }

    }

    for(int i=;i<=n;i++){

        int ans=;

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

            (ans+=(ll)f[i][j]*j%p)%=p;

        write(ans);putchar(' ');

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ5340 & 洛谷4564 & LOJ2552：[CTSC2018]假面——题解

最新文章

热门文章