結果
問題 | No.802 だいたい等差数列 |
ユーザー | pazzle1230 |
提出日時 | 2019-03-30 15:05:37 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 213 ms / 2,000 ms |
コード長 | 3,876 bytes |
コンパイル時間 | 2,900 ms |
コンパイル使用メモリ | 166,832 KB |
実行使用メモリ | 26,404 KB |
最終ジャッジ日時 | 2023-08-09 07:17:13 |
合計ジャッジ時間 | 13,217 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 210 ms
26,204 KB |
testcase_01 | AC | 207 ms
26,396 KB |
testcase_02 | AC | 209 ms
26,396 KB |
testcase_03 | AC | 211 ms
26,080 KB |
testcase_04 | AC | 212 ms
26,128 KB |
testcase_05 | AC | 211 ms
26,260 KB |
testcase_06 | AC | 211 ms
26,384 KB |
testcase_07 | AC | 210 ms
26,404 KB |
testcase_08 | AC | 206 ms
26,152 KB |
testcase_09 | AC | 209 ms
26,228 KB |
testcase_10 | AC | 209 ms
26,260 KB |
testcase_11 | AC | 210 ms
26,204 KB |
testcase_12 | AC | 209 ms
26,192 KB |
testcase_13 | AC | 211 ms
26,264 KB |
testcase_14 | AC | 213 ms
26,332 KB |
testcase_15 | AC | 211 ms
26,264 KB |
testcase_16 | AC | 210 ms
26,268 KB |
testcase_17 | AC | 203 ms
26,192 KB |
testcase_18 | AC | 207 ms
26,264 KB |
testcase_19 | AC | 204 ms
26,328 KB |
testcase_20 | AC | 208 ms
26,380 KB |
testcase_21 | AC | 204 ms
26,156 KB |
testcase_22 | AC | 208 ms
26,400 KB |
testcase_23 | AC | 204 ms
26,188 KB |
testcase_24 | AC | 208 ms
26,348 KB |
testcase_25 | AC | 206 ms
26,388 KB |
testcase_26 | AC | 205 ms
26,192 KB |
testcase_27 | AC | 213 ms
26,160 KB |
testcase_28 | AC | 209 ms
26,160 KB |
testcase_29 | AC | 212 ms
26,208 KB |
testcase_30 | AC | 207 ms
26,336 KB |
testcase_31 | AC | 207 ms
26,400 KB |
testcase_32 | AC | 207 ms
26,400 KB |
testcase_33 | AC | 205 ms
26,272 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF_LL (int64)1e18 #define INF (int32)1e9 #define REP(i, n) for(int64 i = 0;i < (n);i++) #define FOR(i, a, b) for(int64 i = (a);i < (b);i++) #define all(x) x.begin(),x.end() #define fs first #define sc second using int32 = int_fast32_t; using uint32 = uint_fast32_t; using int64 = int_fast64_t; using uint64 = uint_fast64_t; using PII = pair<int32, int32>; using PLL = pair<int64, int64>; const double eps = 1e-10; template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;} template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;} template<typename T> vector<T> make_v(size_t a){return vector<T>(a);} template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;} template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } template<::std::uint_fast64_t mod> class ModInt{ private: using value_type = ::std::uint_fast64_t; value_type n; public: ModInt() : n(0) {} ModInt(value_type n_) : n(n_ % mod) {} ModInt(const ModInt& m) : n(m.n) {} template<typename T> explicit operator T() const { return static_cast<T>(n); } value_type get() const { return n; } friend ::std::ostream& operator<<(::std::ostream &os, const ModInt<mod> &a) { return os << a.n; } friend ::std::istream& operator>>(::std::istream &is, ModInt<mod> &a) { value_type x; is >> x; a = ModInt<mod>(x); return is; } bool operator==(const ModInt& m) const { return n == m.n; } bool operator!=(const ModInt& m) const { return n != m.n; } ModInt& operator*=(const ModInt& m){ n = n * m.n % mod; return *this; } ModInt pow(value_type b) const{ ModInt ans = 1, m = ModInt(*this); while(b){ if(b & 1) ans *= m; m *= m; b >>= 1; } return ans; } ModInt inv() const { return (*this).pow(mod-2); } ModInt& operator+=(const ModInt& m){ n += m.n; n = (n < mod ? n : n - mod); return *this; } ModInt& operator-=(const ModInt& m){ n += mod - m.n; n = (n < mod ? n : n - mod); return *this; } ModInt& operator/=(const ModInt& m){ *this *= m.inv(); return *this; } ModInt operator+(const ModInt& m) const { return ModInt(*this) += m; } ModInt operator-(const ModInt& m) const { return ModInt(*this) -= m; } ModInt operator*(const ModInt& m) const { return ModInt(*this) *= m; } ModInt operator/(const ModInt& m) const { return ModInt(*this) /= m; } ModInt& operator++(){ n += 1; return *this; } ModInt& operator--(){ n -= 1; return *this; } ModInt operator++(int){ ModInt old(n); n += 1; return old; } ModInt operator--(int){ ModInt old(n); n -= 1; return old; } ModInt operator-() const { return ModInt(mod-n); } }; template<::std::size_t size, ::std::uint_fast64_t mod=1000000007> class Factorial{ private: using value_type = ModInt<mod>; ::std::vector<value_type> fact, inv; public: Factorial() : fact(size+1, 1), inv(size+1, 1){ for(::std::size_t i = 1; i <= size; ++i){ fact[i] = fact[i-1] * value_type(i); inv[i] = fact[i].inv(); } } value_type comb(::std::int64_t a, ::std::int64_t b){ assert(a >= b); assert(b >= 0); return fact[a]*inv[b]*inv[a-b]; } value_type& operator[](::std::size_t k){ return fact[k]; } }; const int64 mod = 1e9+7; using Mint = ModInt<mod>; Factorial<1500000> f; int main(void) { int64 N, M, D1, D2; cin >> N >> M >> D1 >> D2; M -= D1*(N-1) + 1; D2 -= D1; if (M < 0) { cout << 0 << endl; return 0; } Mint res = 0; REP(i, N) { if ((D2+1)*i > M) continue; Mint rest = M-(D2+1)*i; Mint ret = f.comb(rest.get()+N, rest.get()) * f.comb(N-1, i); if (i%2) res -= ret; else res += ret; } cout << res << endl; }