結果
問題 | No.1127 変形パスカルの三角形 |
ユーザー | HEXAebmr |
提出日時 | 2020-07-28 02:00:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 188 ms / 1,500 ms |
コード長 | 4,470 bytes |
コンパイル時間 | 1,290 ms |
コンパイル使用メモリ | 112,020 KB |
実行使用メモリ | 97,264 KB |
最終ジャッジ日時 | 2024-06-28 20:28:46 |
合計ジャッジ時間 | 7,034 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 133 ms
97,160 KB |
testcase_01 | AC | 145 ms
97,184 KB |
testcase_02 | AC | 147 ms
97,060 KB |
testcase_03 | AC | 155 ms
97,060 KB |
testcase_04 | AC | 147 ms
97,200 KB |
testcase_05 | AC | 146 ms
97,036 KB |
testcase_06 | AC | 155 ms
97,040 KB |
testcase_07 | AC | 162 ms
97,180 KB |
testcase_08 | AC | 143 ms
97,236 KB |
testcase_09 | AC | 176 ms
97,264 KB |
testcase_10 | AC | 176 ms
97,032 KB |
testcase_11 | AC | 173 ms
97,188 KB |
testcase_12 | AC | 163 ms
97,168 KB |
testcase_13 | AC | 183 ms
97,052 KB |
testcase_14 | AC | 188 ms
97,220 KB |
testcase_15 | AC | 160 ms
97,208 KB |
testcase_16 | AC | 184 ms
97,084 KB |
testcase_17 | AC | 179 ms
97,192 KB |
testcase_18 | AC | 174 ms
97,040 KB |
testcase_19 | AC | 172 ms
97,168 KB |
testcase_20 | AC | 163 ms
97,172 KB |
testcase_21 | AC | 184 ms
97,060 KB |
testcase_22 | AC | 158 ms
97,092 KB |
testcase_23 | AC | 150 ms
97,160 KB |
testcase_24 | AC | 151 ms
97,144 KB |
testcase_25 | AC | 149 ms
97,228 KB |
testcase_26 | AC | 158 ms
97,032 KB |
testcase_27 | AC | 156 ms
97,096 KB |
testcase_28 | AC | 153 ms
97,192 KB |
testcase_29 | AC | 156 ms
97,260 KB |
testcase_30 | AC | 145 ms
97,236 KB |
testcase_31 | AC | 157 ms
97,116 KB |
ソースコード
#include <iostream> #include <iomanip> #include <string> #include <stack> #include <vector> #include <complex> #include <math.h> #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <iterator> #include <map> #include <set> #include <queue> #include <list> #include <regex> #include <limits> #include <time.h> #include <cstdint> using namespace std; using pii = pair<int,int>; using ll=long long; using ld=long double; #define pb push_back #define mp make_pair #define sc second #define fr first #define stpr setprecision #define cYES cout<<"YES"<<endl #define cNO cout<<"NO"<<endl #define cYes cout<<"Yes"<<endl #define cNo cout<<"No"<<endl #define rep(i,n) for(ll i=0;i<(n);++i) #define Rep(i,a,b) for(ll i=(a);i<(b);++i) #define rrep(i,n) for(ll i=n-1;i>=0;i--) #define rRep(i,a,b) for(ll i=a;i>=b;i--) #define crep(i) for(char i='a';i<='z';++i) #define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;}); #define ALL(x) (x).begin(),(x).end() #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define endl '\n' int ctoi(const char c){ if('0' <= c && c <= '9') return (c-'0'); return -1; } ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));} ll lcm(ll a,ll b){return a*b/gcd(a,b);} constexpr ll MOD=1000000007; constexpr ll INF=1000000011; constexpr ll MOD2=998244353; constexpr ll LINF = 1001002003004005006ll; constexpr ld EPS=10e-8; template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; } template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; } template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;} template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;} template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;} template<class T> ostream& operator<<(ostream& os, vector<T>& v){ for(auto i=begin(v); i != end(v); ++i){ if(i !=begin(v)) os << ' '; os << *i; } return os; } // modint template <std::uint_fast64_t Modulus> class modint { using u64 = std::uint_fast64_t; public: u64 a; constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} constexpr u64 &value() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } 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 { a += rhs.a; if (a >= Modulus) { a -= Modulus; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (a < rhs.a) { a += Modulus; } a -= rhs.a; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { a = a * rhs.a % Modulus; return *this; } constexpr modint &operator/=(modint rhs) noexcept { u64 exp = Modulus - 2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } }; const int MAX = 4000003; long long fac[MAX], finv[MAX], inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int main() { // 前処理 COMinit(); ll A,B,N,M; cin>>A>>B>>N>>M; A%=MOD;B%=MOD; modint<MOD> ANS=0; if(M<=N+1){ ANS+=A*COM(N-1,M-1); } M--; if(M>0){ ANS+=B*COM(N-1,M-1); } cout << ANS.a << endl; ANS=0; rep(i,N+2){ modint<MOD> K=0; if(i<N+1){ K+=A*COM(N-1,i); } if(i>0){ K+=B*COM(N-1,i-1); } ANS+=K*K; } cout << ANS.a << endl; }