题解：P14446 [ICPC 2025 Xi'an Practice] Zelda

· · 题解

考虑经典技巧 E(x)= \sum i\times P(x=i) = \sum P(x\ge i)。

所以可以枚举 i，然后将 \ge i 的看成 1，< i 的看成 0。P(x\ge i) 就是最后 x=1 的概率，正确性显然，这个概率容易单次 O(n) 计算，所以这样即可做到 O(qnr)，不过好像直接 dp 也可以做到这个复杂度。

首先把概率变成方案数除以总方案数，总方案数是容易的先不管，那么只需要求出方案数即可。

设 mx=\max\limits_{i=1}^n \max(a_i,b_i)。

对于 r\in [l,mx) 可以直接暴力计算。

对于 r\in [mx,10^9] 可以通过分类讨论发现方案数是关于 r 的最多为 2n+1 次多项式，直接取 r=mx,mx+1,\dots,mx+2n+2 拉插即可做到单次询问 O(n)。

因为我们还需要求一个前缀和，所以拉插上界需要取 2n+2。

总复杂度 O(n^3+qn)，std 只跑了 500ms，不过好像为了测试评测机压力开了 3s。

#define LOCAL
#include<bits/stdc++.h>
#define int long long
using namespace std;

namespace ly{
    namespace IO{
        #ifndef LOCAL
            #define SIZE (1<<20)
            char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(p3=out,1,SIZE,stdout))
            #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        template<typename type>
        inline void read(type &x){
            x=0;bool flag(0);char ch=getchar();
            while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            flag?x=-x:0;
        }
        template<typename type>
        inline void write(type x,bool flag=1){
            x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
            do Stack[++top]=x%10,x/=10;while(x);
            while(top) putchar(Stack[top--]|48);
            flag?putchar('\n'):putchar(' ');
        }
        #ifndef LOCAL
            #undef SIZE
            #undef getchar
            #undef putchar
            #undef flush
        #endif
    }
}using namespace ly::IO;

const int N=1010,mod=1e9+7;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int x[N],y[N],z[N],f[N],posy[N],posx[N];
int F[N],G[N],pre[N],suf[N];
int a[N],ansr[N],n,q,m,l,qaq;
int lacha(int k){
    pre[0]=1;
    for(int i=1;i<=qaq+1;i++)pre[i]=pre[i-1]*(k-i)%mod;
    suf[qaq+2]=1;
    for(int i=qaq+1;i>=1;i--)suf[i]=suf[i+1]*(k-i)%mod;
    int ans=0;
    for(int i=1;i<=qaq+1;i++){
        int wa=pre[i-1]*suf[i+1]%mod;
        int wb=G[i-1]*G[qaq+1-i]%mod;
        if((qaq+1-i)&1)wb=(mod-wb);
        ans=(ans+posy[i]*wa%mod*wb%mod)%mod;
    }
    return (ans+mod)%mod;
}
signed main(){
    F[0]=1;
    for(int i=1;i<N;i++)F[i]=F[i-1]*i%mod;
    G[N-1]=qpow(F[N-1],mod-2);
    for(int i=N-1;i>=1;i--)G[i-1]=G[i]*i%mod;
    read(n);read(q);read(l);
    int mx=l;
    for(int i=1;i<=n;i++)read(a[2*i-1]);
    for(int i=1;i<=n;i++)read(a[2*i]);
    int cnt=1;
    for(int i=1;i<=2*n;i++)mx=max(mx,a[i]),cnt+=(a[i]==0);
    m=n<<1;
    qaq=m+2; 
    int cntt=0;
    for(int r=l;r<=mx+qaq;r++){
        z[0]=r-l+1;
        for(int i=1;i<=m;i++){
            z[i]=z[i-1];
            if(!a[i])
                z[i]=z[i]*(r-l+1)%mod;
        }
        int tmp=max(r,mx);
        for(int i=l;i<=tmp;i++){
            f[0]=max(0ll,r-i+1);
            for(int j=1;j<=m;j++){
                if(a[j]){
                    x[j]=(a[j]<i);
                    y[j]=(a[j]>=i);
                }else{
                    if(i<=r){
                        x[j]=i-l;
                        y[j]=r-i+1; 
                    }else{
                        x[j]=r-l+1;
                        y[j]=0;
                    }   
                }
                f[j]=(y[j]*z[j-1]+f[j-2]*y[j-1]%mod*x[j])%mod;
            }
            if(l==i&&r==l)
                cntt=f[m];
            ansr[r]+=f[m];  
        }
        ansr[r]%=mod;
        if(r>=mx){
            posx[r-mx+1]=r-mx+1;
            posy[r-mx+1]=ansr[r];
        }
    }
    while(q--){
        int r;
        read(r);
        int w=qpow(r-l+1,cnt);
        if(r<mx){
            write((ansr[r]*qpow(w,mod-2)%mod+(l-1)*cntt%mod)%mod);
            continue;
        }
        write((lacha(r-mx+1)*qpow(w,mod-2)%mod+(l-1)*cntt%mod)%mod);
    }
    return 0;
}