Codeforces 1288C Two Arrays (R1600)

codeforces.com

問題

整数 $N,M$ が与えられます。長さ $N$ の数列 $a,b$ のペアであって、次の条件を満たすものの個数を求めてください。

$1 \le a_i,\ b_i \le M\ (1 \le i \le N)$
$a_i \le a_{i+1}\ (1 \le i \le N-1)$
$b_i \ge b_{i+1}\ (1 \le i \le N-1)$
$a_i \le b_i\ (1 \le i \le N)$

制約

$1 \le N \le 10$
$1 \le M \le 1000$

考察

条件を図にすると、赤の□で囲んだ部分の不等号が無くても十分だと分かります。 f:id:tekihei:20200121211206j:plain
よって、以下の条件を満たす $a,b$ の個数を数えれば良いです。

$1 \le a_1 \le a_2 \le \cdots \le a_N \le b_N \le b_{N-1} \le \cdots \le b_1 \le M$

これは $M$ 種類のものから重複を許して $2N$ 個取る場合の数に等しく、 $\binom{M+2N-1}{2N}$ 通りです。

#include<bits/stdc++.h>
using namespace std;

using Lint=long long;
template<int mod> class ModInt
{
 private:
    Lint val;
 public:
    Lint value(){ return val; }
    ModInt(Lint x=0){ val=x%mod; }
    ModInt pow(int n){
        ModInt res(1),x(val);
        while(n>0){ if(n&1) res*=x; x*=x; n>>=1; }
        return res;
    }
    ModInt inv(){ return pow(mod-2); }
    ModInt& operator+=(ModInt rhs){ val+=rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator-=(ModInt rhs){ val+=mod-rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator*=(ModInt rhs){ val=val*rhs.val%mod; return *this; }
    ModInt& operator/=(ModInt rhs){ *this*=rhs.inv(); return *this; }
    ModInt operator+(ModInt rhs){ return ModInt(val)+=rhs; }
    ModInt operator-(ModInt rhs){ return ModInt(val)-=rhs; }
    ModInt operator*(ModInt rhs){ return ModInt(val)*=rhs; }
    ModInt operator/(ModInt rhs){ return ModInt(val)/=rhs; }
};
using mint=ModInt<1000000007>;

template<typename T> class BiCoef
{
 public:
    vector<T> fact,ifact,inv;
    BiCoef(int N):fact(N+1),ifact(N+1),inv(N+1){
        fact[0]=ifact[N]=inv[0]=1;
        for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i;
        ifact[N]/=fact[N];
        for(int i=N-1;i>=0;i--) ifact[i]=ifact[i+1]*(i+1);
        for(int i=1;i<=N;i++) inv[i]=ifact[i]*fact[i-1];
    }
    T comb(int n,int k){
        if(n<0 or k<0 or n<k) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main()
{
   int M,N; cin>>M>>N; // max value, length
   BiCoef<mint> bc(M+2*N);
   cout<<bc.comb(M+2*N-1,2*N).value()<<endl;
   return 0;
}