Codeforces Global Round 21 E()

E. Placing Jinas

题链
稍微手写一下发现就是一个杨辉三角
然后我们知道杨辉三角第n行第m个是C（m-1，n-1） 我们对应转化过来就是C（n+m-2,m-1)
然后我们注意处理的组合数到4e5因为最大是n+m-2

int a[N],b[N];
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return a[x]*b[y]%mod*b[x-y]%mod;
}
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=0;i<=n;i++)cin>>a[i];
    int ans=0;
    for(int i=1;i<=a[0]+1;i++){
        int m=upper_bound(all(a),i,greater<>())-a.begin();
        (ans+=C(i+1+m-2,m-1))%=mod;
    }
    cout<<ans<<endl;
}
————————

E. Placing Jinas

题链
稍微手写一下发现就是一个杨辉三角
然后我们知道杨辉三角第n行第m个是C（m-1，n-1） 我们对应转化过来就是C（n+m-2,m-1)
然后我们注意处理的组合数到4e5因为最大是n+m-2

int a[N],b[N];
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(res*a)%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int C(int x,int y){
    if(x<0||y<0||x<y)return 0;
    return a[x]*b[y]%mod*b[x-y]%mod;
}
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=0;i<=n;i++)cin>>a[i];
    int ans=0;
    for(int i=1;i<=a[0]+1;i++){
        int m=upper_bound(all(a),i,greater<>())-a.begin();
        (ans+=C(i+1+m-2,m-1))%=mod;
    }
    cout<<ans<<endl;
}