結果

問題 No.1520 Zigzag Sum
ユーザー ytqm3ytqm3
提出日時 2021-05-28 22:59:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 262 ms / 2,000 ms
コード長 4,269 bytes
コンパイル時間 2,109 ms
コンパイル使用メモリ 203,388 KB
実行使用メモリ 7,212 KB
最終ジャッジ日時 2024-11-07 10:17:55
合計ジャッジ時間 4,438 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
7,168 KB
testcase_01 AC 8 ms
7,168 KB
testcase_02 AC 180 ms
7,168 KB
testcase_03 AC 258 ms
7,212 KB
testcase_04 AC 258 ms
7,156 KB
testcase_05 AC 262 ms
7,168 KB
testcase_06 AC 255 ms
7,076 KB
testcase_07 AC 248 ms
7,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<u64 mod>class modint{
public:
  u64 val;
  constexpr modint(const u64 x=0) noexcept:val(x%mod){}
  constexpr u64 &value() noexcept{
    return val;
  }
  constexpr const u64 &value() const noexcept{
    return val;
  }
  constexpr modint operator+(const modint rhs) const noexcept{
    return modint(*this)+=rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept{
    return modint(*this)-=rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept{
    return modint(*this)*=rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept{
    return modint(*this)/=rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept{
    val+=rhs.val;
    if(val>=mod){
      val-=mod;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept{
    if(val<rhs.val){
      val+=mod;
    }
    val-=rhs.val;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept{
    val=val*rhs.val%mod;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept{
    u64 exp=mod-2;
    while(exp){
      if(exp&1){
        (*this)*=rhs;
      }
      rhs*=rhs;
      exp>>=1;
    }
    return *this;
  }
};

void scan(){}

template<typename T,class... Args>
void scan(T& n,Args&... args){
  cin>>n;
  scan(args...);
}

template<typename T>
void scan_vec(T start,T end){
  T now=start;
  for(;now!=end;++now){
    cin>>(*now);
  }
}

void print(){}

template<typename T,class... Args>
void print(T n,Args... args){
  cout<<n;
  print(args...);
}

template<typename T>
void println(T n){
  cout<<n<<endl;
}

template<typename T,class... Args>
void println(T n,Args... args){
  cout<<n<<' ';
  println(args...);
}

template<typename T>
void print_vec(T start,T end){
  if(start!=end){
    T now=start;
    cout<<(*now);
    ++now;
    for(;now!=end;++now){
      cout<<' '<<(*now);
    }
  }
  cout<<endl;
}

template<typename T>
vector<T> div_enum(T n){
  vector<T> res;
  for(T i=1;i*i<=n;++i){
    if(n%i!=0){
      continue;
    }
    res.push_back(i);
    if(i*i!=n){
      res.push_back(n/i);
    }
  }
  sort(res.begin(),res.end());
  return res;
}

template<typename T>
vector<pair<T,T>> prime_fact(T n){
  vector<pair<T,T>> res;
  for(T i=2;i*i<=n;++i){
    if(n%i!=0){
      continue;
    }
    T ex=0;
    while(n%i==0){
      n/=i;
      ex+=1;
    }
    res.push_back({i,ex});
  }
  if(n!=1){
    res.push_back({n,1});
  }
  return res;
}

template<typename T,typename U>
T power(T a,U n)
{
  T res=1;
  while(n){
    res*=(n&1)?a:1;
    a*=a;
    n>>=1;
  }
  return res;
}

template<typename T>
struct combination
{
  vector<T> fact;
  combination(const int Max):fact(Max+1,1){
    for(int i=2;i<=Max;++i){
      fact[i]=fact[i-1]*i;
    }
  }
  template<typename U>
  T nCk(U n,U k){
    if(n<k||n<0||k<0){
      return 0;
    }
    return fact[n]/fact[k]/fact[n-k];
  }
};


template<typename T>
struct RSQ{
  int N;
  vector<T> bit;
  RSQ(int size):N(size+1),bit(size+1){};
  void add(int a,T x){
    a+=1;
    for(int i=a;i<N;i+=(i&(-i))){
      bit[i]+=x;
    }
  }
  T sum(int n){
    T res=0;
    for (int i=n;i>0;i-=(i&(-i))){
      res+=bit[i];
    }
    return res;
  }
};

template<typename T>
struct RmQ{
  const T INF=numeric_limits<T>::max();
  int n=-1;
  vector<T> dat;
  RmQ(int n_):dat(n_*4,INF) {
    int x=1;
    while(x<n_){
      x*=2;
    }
    n=x;
  }
  void update(int i,T x){
    i+=n-1;
    dat[i]=x;
    while(i){
      i=(i-1)/2;
      dat[i]=min(dat[i*2+1],dat[i*2+2]);
    }
  }
  T query(int a,int b){
    return query_sub(a,b,0,0,n);
  }
  T query_sub(int a,int b,int k,int l,int r){
    if(r<=a||b<=l){
      return INF;
    }
    else if(a<=l&&r<=b){
      return dat[k];
    }
    else{
      T vl=query_sub(a,b,k*2+1,l,(l+r)/2);
      T vr=query_sub(a,b,k*2+2,(l+r)/2,r);
      return min(vl,vr);
    }
  }
};

int main(){
  typedef modint<1000000007> mint;
  combination<mint> COM(5e5);
  int t;
  scan(t);
  for(int i=0;i<t;++i){
    int H,W;
    scan(H,W);
    if(H==1||W==1){
      println(0);
      continue;
    }
    int h=H-1,w=W-1;
    mint x=COM.nCk(h+w-1,h-1)*(w+1);
    mint y=COM.nCk(h+w-1,h-1);
    println(((x-y)*2).val);
  }
  return 0;
}
0