結果
問題 | No.997 Jumping Kangaroo |
ユーザー | toma |
提出日時 | 2020-02-21 22:43:51 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,881 bytes |
コンパイル時間 | 1,761 ms |
コンパイル使用メモリ | 173,840 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-17 07:56:04 |
合計ジャッジ時間 | 2,581 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
ソースコード
#include"bits/stdc++.h" using namespace std; #define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) REP((i),0,(n)) using ll = long long; struct ModInt { static const ll MOD = 1000000007; // constructors etc ModInt() :num(1ll) {} ModInt(ll num_) :num(num_%MOD) {} ModInt(const ModInt& modint) :num(modint.num%MOD) {} ll get()const { return num; } // operator etc // operator ll() const { return num; } // ll operator*() { return num; } ModInt& operator+=(const ModInt& r) { (num += r.num) %= MOD; return *this; } ModInt& operator-=(const ModInt& r) { (num += -r.num + MOD) %= MOD; return *this; } ModInt& operator*=(const ModInt& r) { (num *= r.num) %= MOD; return *this; } ModInt& operator/=(const ModInt& r) { (num *= r.inv().num) %= MOD; return *this; } ModInt pow(const ModInt& r)const { ll res = 1; ll x = num; ll n = r.num; while (n > 0) { if (n & 1)res = (res*x) % MOD; x = (x*x) % MOD; n >>= 1; } return res; } ModInt inv()const { return this->pow(MOD - 2); } ModInt operator+(const ModInt& r)const { return ModInt(*this) += r; } ModInt operator-(const ModInt& r)const { return ModInt(*this) -= r; } ModInt operator*(const ModInt& r)const { return ModInt(*this) *= r; } ModInt operator/(const ModInt& r)const { return ModInt(*this) /= r; } ModInt operator+(const ll& r)const { return *this + ModInt(r); } ModInt operator-(const ll& r)const { return *this - ModInt(r); } ModInt operator*(const ll& r)const { return *this * ModInt(r); } ModInt operator/(const ll& r)const { return *this / ModInt(r); } private: ll num; }; ostream& operator<<(ostream& stream, const ModInt& val) { stream << val.get(); return stream; } using vec = vector<ModInt>; using mat = vector<vec>; //A*Bの計算 mat mul(const mat& A, const mat& B) { mat C(A.size(), vec(B[0].size(), 0)); rep(i, A.size())rep(k, B.size())rep(j, B[0].size()) C[i][j] = C[i][j] + A[i][k] * B[k][j]; return C; } //A^Kの計算 mat pow(mat A, ll N) { mat B(A.size(), vec(A.size(), 0)); rep(i, A.size())B[i][i] = 1; while (N > 0) { if (N & 1)B = mul(B, A); A = mul(A, A); N >>= 1; } return B; } int main() { ll N, W, K; cin >> N >> W >> K; vector<ll> A(N); rep(i, N)cin >> A[i]; const int W2 = 2 * W + 1; vector<ModInt> dp(W2, 0); dp[0] = 1; rep(now, W2)for (ll step : A) if (now + step < W2)dp[now + step] += dp[now]; ModInt n1 = dp[W]; ModInt n2 = dp[W2 - 1] - n1 * n1; if (K <= 1) { cout << (K == 1 ? n1 : dp[W2 - 1]) << endl; return 0; } mat B = { {n1,n2},{1,0} }; B = pow(B, K - 2); ModInt res = B[0][0] * dp[W2 - 1] + B[0][1] * n1; cout << res << endl; return 0; }