CF1194F Crossword Expert（数论，组合数学）

系统管理员 2021-11-22 15:08 250阅读 0赞

不难的一题。不知道为什么能 $2500$……

不过场上推错了一直不会优化……

首先考虑 $f\_i$ 表示恰好做完前 $i$ 道题的概率。

这样很难算。修改一下，$f\_i$ 表示做完至少 $i$ 道题的概率。

答案就是 $\\sum\\limits\_\{i=0\}^ni(f\_i-f\_\{i+1\})=\\sum\\limits\_\{i=1\}^nf\_i$。

由于每道题只可能多用至多一秒，考虑 $dp\[i\]\[j\]$ 为前 $i$ 道题恰好SB $j$ 次的概率。

初始状态是 $dp\[0\]\[0\]=1$。转移是 $dp\[i\]\[j\]=\\dfrac\{1\}\{2\}(f\[i-1\]\[j\]+f\[i-1\]\[j-1\])$。

盯着式子看不难看出 $dp\[i\]\[j\]=(\\dfrac\{1\}\{2\})^i\\dbinom\{i\}\{j\}$。用实际意义也不难理解。

（场上就是这里推成了 $(\\dfrac\{1\}\{2\})^\{i+j\}\\dbinom\{i+j\}\{i\}$ 就自闭了……）

那么有 $f\_i=\\sum\\limits\_\{j=0\}^\{r\_i\}dp\[i\]\[j\]=(\\dfrac\{1\}\{2\})^i\\sum\\limits\_\{j=0\}^\{r\_i\}\\dbinom\{i\}\{j\}$。其中 $r\_i=T-\\sum\\limits\_\{j=1\}^it\_j$，表示最多允许SB几次。（其实要和 $i$ 取个 $\\min$，但是不影响，可以想一想为什么）

问题就是求 $\\sum\\limits\_\{j=0\}^\{r\_i\}\\dbinom\{i\}\{j\}$ 了。接下来是一个很妙的做法。

首先 $i=1$ 时直接暴力。

然后 $\\sum\\limits\_\{j=0\}^\{r\_i\}\\dbinom\{i+1\}\{j\}=\\sum\\limits\_\{j=0\}^\{r\_i\}(\\dbinom\{i\}\{j\}+\\dbinom\{i\}\{j-1\})=2\\sum\\limits\_\{j=0\}^\{r\_i\}\\dbinom\{i\}\{j\}-\\dbinom\{i\}\{r\_i\}$。可以直接递推。

由于 $r\_i$ 单调递减，递推完之后把 $r\_\{i+1\}+1$ 到 $r\_i$ 的组合数都删掉就行了。

实现优秀一点可以做到 $O(n)$。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=200020,mod=1000000007,inv2=500000004;
    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)
    #define MEM(x,v) memset(x,v,sizeof(x))
    inline ll read(){
        ll x=0,f=0;char ch=getchar();
        while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
        while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
        return f?-x:x;
    }
    int n,t[maxn],fac[maxn],inv[maxn],invfac[maxn],f[maxn],ans,pro=1;
    ll r[maxn];
    int C(int n,ll m){
        if(n<m) return 0;
        return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
    }
    int main(){
        n=read();r[0]=read();
        FOR(i,1,n) t[i]=read();
        FOR(i,1,n) r[i]=r[i-1]-t[i];
        fac[0]=fac[1]=inv[1]=invfac[0]=invfac[1]=1;
        FOR(i,2,n){
            fac[i]=1ll*fac[i-1]*i%mod;
            inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
            invfac[i]=1ll*invfac[i-1]*inv[i]%mod;
        }
        FOR(i,0,min(1ll,r[1])) f[1]=(f[1]+C(1,i))%mod;
        FOR(i,2,n){
            if(r[i]<0) break;
            f[i]=(2ll*f[i-1]-C(i-1,r[i-1])+mod)%mod;
            ROF(j,min<ll>(i,r[i-1]),r[i]+1) f[i]=(f[i]-C(i,j)+mod)%mod;
        }
        FOR(i,1,n){
            if(r[i]<0) break;
            pro=1ll*pro*inv2%mod;
            ans=(ans+1ll*pro*f[i])%mod;
        }
        printf("%d\n",ans);
    }

转载于:https://www.cnblogs.com/1000Suns/p/11203600.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/1bfedba206a043469d738905203f1b75.png