結果
問題 | No.1474 かさまJ |
ユーザー |
|
提出日時 | 2021-04-10 01:04:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,500 ms |
コード長 | 14,354 bytes |
コンパイル時間 | 1,736 ms |
コンパイル使用メモリ | 146,420 KB |
実行使用メモリ | 153,084 KB |
最終ジャッジ日時 | 2024-06-25 13:48:09 |
合計ジャッジ時間 | 5,166 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
153,076 KB |
testcase_01 | AC | 80 ms
152,948 KB |
testcase_02 | AC | 78 ms
152,948 KB |
testcase_03 | AC | 77 ms
153,080 KB |
testcase_04 | AC | 80 ms
153,080 KB |
testcase_05 | AC | 114 ms
153,076 KB |
testcase_06 | AC | 85 ms
152,952 KB |
testcase_07 | AC | 79 ms
153,076 KB |
testcase_08 | AC | 80 ms
152,956 KB |
testcase_09 | AC | 130 ms
152,952 KB |
testcase_10 | AC | 79 ms
153,080 KB |
testcase_11 | AC | 76 ms
153,076 KB |
testcase_12 | AC | 79 ms
153,080 KB |
testcase_13 | AC | 133 ms
153,076 KB |
testcase_14 | AC | 95 ms
153,080 KB |
testcase_15 | AC | 86 ms
153,084 KB |
testcase_16 | AC | 79 ms
153,080 KB |
testcase_17 | AC | 97 ms
153,076 KB |
testcase_18 | AC | 148 ms
152,956 KB |
testcase_19 | AC | 161 ms
152,952 KB |
testcase_20 | AC | 164 ms
152,952 KB |
ソースコード
// // S i r o t a n w a t c h e s o v e r y o u . // // ...Jggg+J+JJJg@NQmgJa....., // ....gH@@@@HHB""""7"YYYYHMMMMMMM@@@@@@@Hma,. // ...JH@@MMHY"! ? __""YH@@@@N&... // ..JH@@HY"~ _TW@@@Mme. // .Jg@@#"= _TTM@@N.. // .Jg@@MY! ?T@@@h,. // .-@@@B! (TM@@@L // .(H@MY ?W@@@+ // .W@@@ .T@@@[ // .d@@M! .T@@N, // .d@M@' -W@@o. // (@@M\ ?M@N, // -d@M% .., .., j@@b // d@@M= TM9 ?MD W@@[ // .H@M: .W@H, // H@Ht ,@@# // (@@M~ .@@h. // .@@M% ..gmHHJ. .JdHga. .H@@e // j@@#_ .@@@@@@@b J@@@@@@@h. .H@@\ // d@@@ .4@@@@@@MF (@@@@@@@@ H@@b // d@@[ ?"BMY"= .d@@@@H, ?TWHHY"! d@@e // J@@b .JJJ-.., ,@@@@@@M% ......... -@@@M. // ?@@M\ ?YHHM@@@@b .. .W@@HP X@@HMWY"= d@@@# // ,@@@L. ?H@Ng&+gd@@#H@@NHaJ+gH@[ J@@@] // X@@@[ ...... ?"YYYYY"" ?"YHHHB"^ ..... (@@@# // WH@N+. .W@@@@MHB= .TWH@M@Hmc .H@@M~ // .H@@@@N, _!~ .d@@@N, // .J@@#T@@@N, .d@@@@@@@b. // (@@@@! .T@@@n, .(H@@@H>.W@@@x // (@@@F 4@@@@MaJ. .d@@@@Y77 4@@@r //.H@@P ?TM@@@@N... .-JH@HMY= d@@N, //(@@@F ?"WM@@@MQa-,. .(J(JN@@M#" Z@@@L // d@@H, (M@@@@@@@Ng&maJ.... .. ...J.J+W@@@@@@HY! .dH@b // ?M@@@N&. ..(JW@@@MM"?7""TYHMH@@HH@@@@@HHHgkHagHa(mggdmmagH@H@@Q@@HMMMHY"7!TMM@@@HaJ,. ..H@@@M^ // ?"W@@@@MN@@@@@H@@MMY" _???!"= ?WMMBYYTMH=7""Y@""?"~^ _"YM@@@@@@@@MH@@@@@#"^ // ?77WMMMYB""! _7"WWMMMY"7= // need #include <iostream> #include <algorithm> // data structure #include <bitset> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <cstring> #include <utility> #include <vector> #include <complex> //#include <deque> #include <valarray> #include <unordered_map> #include <unordered_set> #include <array> // etc #include <cassert> #include <cmath> #include <functional> #include <iomanip> #include <chrono> #include <random> #include <numeric> #include <fstream> //std::ifstream ifs("d.in"); //auto& scan_in = ifs; auto& scan_in = std::cin; auto& scan_out = std::cout; // input #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); template<typename T> void MACRO_VAR_Scan(T& t) { scan_in >> t; } template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest& ...rest) { scan_in >> first; MACRO_VAR_Scan(rest...); } #define VEC_ROW(type, n, ...)std::vector<type> __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int w_=0; w_<n; ++w_){MACRO_VEC_ROW_Scan(w_, __VA_ARGS__);} template<typename T> void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); } template<typename First, typename...Rest>void MACRO_VEC_ROW_Init(int n, First& first, Rest& ...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); } template<typename T> void MACRO_VEC_ROW_Scan(int p, T& t) { scan_in >> t[p]; } template<typename First, typename...Rest>void MACRO_VEC_ROW_Scan(int p, First& first, Rest& ...rest) { scan_in >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); } #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)scan_in>>i; #define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& R:c)for(auto& w:R)scan_in>>w; // output template<typename T>void MACRO_OUT(const T t) { scan_out << t; } template<typename First, typename...Rest>void MACRO_OUT(const First first, const Rest...rest) { scan_out << first << ' '; MACRO_OUT(rest...); } #define OUT(...) MACRO_OUT(__VA_ARGS__); #define FOUT(n, dist) scan_out<<std::fixed<<std::setprecision(n)<<(dist); #define SOUT(n, c, dist) scan_out<<std::setw(n)<<std::setfill(c)<<(dist); #define VOUT(v) for(size_t i = 0; i < v.size(); ++i) {OUT(v[i]);if(i+1<v.size()){SP}} #define EOUT(...) do{ OUT(__VA_ARGS__)BR; exit(0); }while(0); #define SP scan_out<<' '; #define TAB scan_out<<'\t'; #define BR scan_out<<'\n'; #define SPBR(w, n) scan_out<<(w + 1 == n ? '\n' : ' '); #define ENDL scan_out<<std::endl; #define FLUSH scan_out<<std::flush; #define SHOW(dist) {std::cerr << #dist << "\t: " << (dist) << '\n';} // utility #define ALL(a) (a).begin(),(a).end() #define FOR(w, a, n) for(int w=(a);w<(n);++w) #define REP(w, n) FOR(w, 0, n) #define RFOR(w, a, n) for(int w=(n)-1;w>=(a);--w) #define RREP(w, n) RFOR(w, 0, n) template<class S, class T, class U> bool IN(S a, T x, U b) { return a <= x && x < b; } template<class T> inline bool CHMAX(T& a, const T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool CHMIN(T& a, const T b) { if (a > b) { a = b; return true; } return false; } // test template<class T> using V = std::vector<T>; template<class T> using VV = V<V<T>>; template<typename S, typename T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) { os << '{'; for (size_t i = 0; i < v.size(); ++i) os << v[i] << ((i + 1 < v.size()) ? ',' : '}'); return os; } template<typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& v) { os << '{'; for (auto it = v.cbegin(); it != v.cend();) { os << *it << (++it == v.cend() ? '}' : ','); } return os; } template<typename S, typename T> std::ostream& operator<<(std::ostream& os, const std::map<S, T>& m) { os << '{'; for (auto it = m.cbegin(); it != m.cend();) { os << it->first << ':' << it->second; ++it; os << (it != m.cend() ? ',' : '}'); } return os; } template<typename T> std::ostream& operator<<(std::ostream& os, std::queue<T> q) { os << '<'; while (!q.empty()) { os << q.front(); q.pop(); os << (q.empty() ? '<' : ','); } return os; } template<typename T> std::ostream& operator<<(std::ostream& os, std::stack<T> q) { os << '>'; while (!q.empty()) { os << q.top(); q.pop(); os << (q.empty() ? ']' : ','); } return os; } namespace std { template<typename S, typename T> class numeric_limits<pair<S, T>> { public: static constexpr pair<S, T> max() noexcept { return { numeric_limits<S>::max(), numeric_limits<T>::max() }; } static constexpr pair<S, T> lowest() noexcept { return { numeric_limits<S>::lowest(), numeric_limits<T>::lowest() }; } }; } // type/const using i64 = long long; using u64 = unsigned long long; using ll = long long; using ull = unsigned long long; using ld = long double; using PAIR = std::pair<int, int>; constexpr int INFINT = (1 << 30) - 1; // 1.07x1[i]0^ 9 constexpr int INFINT_LIM = (1LL << 31) - 1; // 2.15x1[i]0^ 9 constexpr long long INFLL = 1LL << 60; // 1.15x1[i]0^18 constexpr long long INFLL_LIM = (1LL << 62) - 1 + (1LL << 62); // 9.22x1[i]0^18 constexpr double EPS = 1e-6; constexpr int MOD = 1000000007; constexpr double PI = 3.141592653589793238462643383279; template<class T, size_t N> void FILL(T(&a)[N], const T& val) { for (auto& x : a) x = val; } template<class ARY, size_t N, size_t M, class T> void FILL(ARY(&a)[N][M], const T& val) { for (auto& b : a) FILL(b, val); } template<class T> void FILL(std::vector<T>& a, const T& val) { for (auto& x : a) x = val; } template<class ARY, class T> void FILL(std::vector<std::vector<ARY>>& a, const T& val) { for (auto& b : a) FILL(b, val); } // ------------>8------------------------>8------------ class ModInt { friend std::istream& operator>>(std::istream& is, ModInt& obj); private: inline ModInt& normUpper() { if (val >= MOD) val -= MOD; return *this; } inline ModInt& normLower() { if (val < 0) val += MOD; return *this; } inline ModInt& norm() { return normUpper(), normLower(); } public: constexpr static int numOfPrecalc = 1000006; static ModInt inv[numOfPrecalc]; int val; ModInt() : val(0) {} ModInt(int n) : val(n) { if (n >= MOD || n <= -MOD) n %= MOD; norm(); } ModInt(long long n) : ModInt((int)(n% MOD)) {} ModInt& operator=(const ModInt& r) { val = r.val; return *this; } ModInt operator+() const { return *this; } ModInt operator-() const { return ModInt(MOD - val); } ModInt& operator+=(const ModInt& r) { val += r.val; return normUpper(); } ModInt& operator-=(const ModInt& r) { val -= r.val; return normLower(); } ModInt& operator*=(const ModInt& r) { val = (long long)val * r.val % MOD; return *this; } ModInt& operator/=(ModInt r) { return *this *= (r.val < numOfPrecalc) ? inv[r.val] : (r ^= MOD - 2); } ModInt& operator^=(int p) { ModInt t(*this); *this = 1; for (; p; p >>= 1, t *= t) if (p & 1) *this *= t; return *this; } const ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; } const ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; } const ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; } const ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; } const ModInt operator^(int p) const { return ModInt(*this) ^= p; } }; const ModInt operator+(int l, const ModInt& r) { return ModInt(l) += r; } const ModInt operator-(int l, const ModInt& r) { return ModInt(l) -= r; } const ModInt operator*(int l, const ModInt& r) { return ModInt(l) *= r; } const ModInt operator/(int l, const ModInt& r) { return ModInt(l) /= r; } std::ostream& operator<<(std::ostream& os, const ModInt& obj) { return os << obj.val; } /* friend */ std::istream& operator>>(std::istream& is, ModInt& obj) { is >> obj.val; obj.norm(); return is; } ModInt ModInt::inv[ModInt::numOfPrecalc]; struct Init_ModInt { Init_ModInt() { ModInt::inv[1] = 1; for (int i = 2; i < ModInt::numOfPrecalc; ++i) ModInt::inv[i] = (MOD - MOD / i) * ModInt::inv[MOD % i]; } } _init_modint; /** ModInt **/ ll powMod(ll n, ll p, ll mod) { ll res = 1; while (p) { if (p & 1) (res *= n) %= mod; (n *= n) %= mod; p >>= 1; } return res; } ll invMod(ll n, ll mod) { return powMod(n, MOD - 2, MOD); } const signed FACT_MAX_N = 1000006; signed fact[FACT_MAX_N]; signed factInv[FACT_MAX_N]; struct INIT_FACT { INIT_FACT() { fact[0] = 1; for (int i = 1; i < FACT_MAX_N; ++i) fact[i] = (long long)i * fact[i - 1] % MOD; factInv[FACT_MAX_N - 1] = powMod(fact[FACT_MAX_N - 1], MOD - 2, MOD); for (int i = FACT_MAX_N - 2; i >= 0; --i) factInv[i] = (long long)(i + 1) * factInv[i + 1] % MOD; } } init_fact; #if true // true if use MOD /* n,r<=10^6, query O(1)*/ ll Permutation(int n, int r) { if (r == 0) return 1; if (n < r) return 0; return (long long)fact[n] * factInv[n - r] % MOD; } ll Combination(int n, int r) { if(0 <= r && r <= n) return (long long)fact[n] * factInv[n - r] % MOD * factInv[r] % MOD; return 0; } ll CombinationWithRepetition(ll n, ll r) { return Combination(n + r - 1, r); } /*n<=10^9, r<=10^5, query O(r)*/ /*ll Combination(ll n, ll r, ll mod) { if (n < r) return 0; ll ans = 1; if (n < 2 * r) r = n - r; for (int i = 1; i <= r; ++i) { ans *= n - i + 1; ans %= mod; ans *= powMod(i, mod - 2, mod); ans %= mod; } return ans; } ll Permutation(int n, int r, int mod) { return Combination(n, r, mod) * fact[r] % MOD; }*/ #else // unuse MOD const signed COMB_MAX_N = 67; // <- max : 67 long long comb[COMB_MAX_N][COMB_MAX_N]; struct INIT_COMB { INIT_COMB() { for (int i = 0; i < COMB_MAX_N; ++i) { for (int j = 0; j <= i; ++j) { if (j == 0 || j == i) comb[i][j] = 1; else comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]; } } } } init_comb; #endif ModInt dp[42][42][20004]; signed main() { INIT; VAR(int, n, mp, mq, l); VEC(int, s, n); dp[0][0][0] = 1; REP(i, n) REP(j, n) { ModInt sum = 0; REP(k, mq + 1) { dp[i + 1][j][k] += dp[i][j][k]; dp[i + 1][j + 1][k] += sum; sum += dp[i][j][k]; if(k - s[i] >= 0) sum -= dp[i][j][k - s[i]]; //FOR(m, 1, s[i] + 1) if (k + m <= mq) dp[i + 1][j + 1][k + m] += dp[i][j][k]; } } ModInt ans = 0; REP(j, n + 1) REP(k, mq + 1) if(dp[n][j][k].val > 0) ans += dp[n][j][k] * Combination(mp - j * l + k + n - 1, n - 1); EOUT(ans); return 0; }