AT3576 Popping Balls

╰+攻爆jí腚メ 2021-12-23 15:23 89阅读 0赞

[AT3576 Popping Balls][]

好题！一种以前没怎么见过的思路！

[%%ywy][ywy]

以什么方式，什么位置统计本质不同的方案，才能不重不漏是处理所有计数问题的主心骨。

本题难以容斥。难以DP。

所以就尝试挖掘性质，**考虑过程！**

首先，红色什么时候都可以选，因为可以选择1

不妨给t定一个位置，**先充分利用t，再用s**，（如果s先用上了，那么t肯定就没意义了）

考虑每个方案是怎样构造出来的，归到合适的t的位置统计。

不妨直接按照“先拿了x个红的，再拿一个蓝的”为标准统计！

为了能涵盖所有之后的决策，让t位于A-(x-1)位置一定最优！**让t拿走这个第一个蓝色**

首先t肯定是\[1,A+1\]的

枚举这个位置t，拿走之后，剩下t-1个红色，B-1个蓝色球

现在，之后的连续B-1个球，**红色和蓝色可以任意拿！**

枚举拿i个红色，贡献C(B-1,i)，剩下t-1-i个红色，i个蓝色

t已经废了。

考虑s放在哪里

同样的，枚举“再拿了y个红色，再拿一个蓝色”，

枚举这个位置s，拿走之后，剩下s-1个红色，i-1个蓝色

现在，之后的连续i-1个球，红色和蓝色可以任意拿！

枚举拿j个红色，贡献C(i-1,j)，剩下若干红色，若干蓝色

s也废了

直接一口气拿完即可。

由于s和t的位置不能再优秀了，每种方案都一定会考虑到！

![1399631-20190602165339389-1087624272.png][]

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    namespace Modulo{
    const int mod=1e9+7;
    int ad(int x,int y){
        return (x+y)>=mod?x+y-mod:x+y;}
    void inc(int &x,int y){x=ad(x,y);}
    int mul(int x,int y){
        return (ll)x*y%mod;}
    void inc2(int &x,int y){x=mul(x,y);}
    int qm(int x,int y=mod-2){
        int ret=1;while(y){
        if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    }
    using namespace Modulo;
    namespace Miracle{
    const int N=2003;
    int A,B;
    int f[N][N];
    int C[N][N];
    int main(){
        rd(A);rd(B);
        C[0][0]=1;
        int lim=max(A,B)+1;
        for(reg i=1;i<=lim;++i){
            C[i][0]=1;
            for(reg j=1;j<=i;++j){
                C[i][j]=ad(C[i-1][j],C[i-1][j-1]);
            }
        }
        for(reg i=1;i<=lim;++i){
            for(reg s=1;s<=lim;++s){
                f[i][s]=ad(f[i][s-1],C[i-1][s-1]);
            }
            for(reg s=1;s<=lim;++s) f[i][s]=ad(f[i][s],f[i][s-1]);
        }
        int ans=0;
        for(reg t=1;t<=A+1;++t){
            for(reg i=0;i<=t-1;++i){
                if(i!=0) ans=ad(ans,mul(C[B-1][i],f[i][t-i]));
                else ans=ad(ans,1);
            }
        }
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

emm，首先发现红色随意拿，s，t为拿蓝色而生！先用t再用s，所以自然就考虑到第一个蓝色在哪里。所以考虑到t放在最优位置上更好。然后任意拿，s同上。

式子的化简就很暴力了其实。

有的时候一些计数题，不妨先枚举最前面一部分的构成，**尽量早或者尽量优**地进行一些决策来不重不漏涵盖情况，所谓**字典序最小的位置统计**

转载于:https://www.cnblogs.com/Miracevin/p/10963431.html

[AT3576 Popping Balls]: https://www.luogu.org/problemnew/show/AT3576
[ywy]: https://www.luogu.org/blog/ywycasm/solution-at3576
[1399631-20190602165339389-1087624272.png]: /images/20211223/1ee1c700e1f8463e97ce4ae238eba2a6.png