結果

問題 No.997 Jumping Kangaroo
ユーザー ミドリムシミドリムシ
提出日時 2020-02-21 21:46:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 8,517 bytes
コンパイル時間 1,925 ms
コンパイル使用メモリ 176,928 KB
実行使用メモリ 4,508 KB
最終ジャッジ日時 2023-07-30 05:45:32
合計ジャッジ時間 3,007 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,508 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

template< int mod >
struct ModInt {
    int x;
    
    ModInt() : x(0) {}
    
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    
    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    
    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }
    
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }
    
    ModInt operator-() const { return ModInt(-x); }
    
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    
    bool operator==(const ModInt &p) const { return x == p.x; }
    
    bool operator!=(const ModInt &p) const { return x != p.x; }
    
    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    
    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    
    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }
    
    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }
    
    static int get_mod() { return mod; }
};

using modint = ModInt< mod >;

template< class T >
struct Matrix {
    vector< vector< T > > A;
    
    Matrix() {}
    
    Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {}
    
    Matrix(size_t n) : A(n, vector< T >(n, 0)) {};
    
    size_t height() const {
        return (A.size());
    }
    
    size_t width() const {
        return (A[0].size());
    }
    
    inline const vector< T > &operator[](int k) const {
        return (A.at(k));
    }
    
    inline vector< T > &operator[](int k) {
        return (A.at(k));
    }
    
    static Matrix I(size_t n) {
        Matrix mat(n);
        for(int i = 0; i < n; i++) mat[i][i] = 1;
        return (mat);
    }
    
    Matrix &operator+=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }
    
    Matrix &operator-=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }
    
    Matrix &operator*=(const Matrix &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector< vector< T > > C(n, vector< T >(m, 0));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                for(int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }
    
    Matrix &operator^=(long long k) {
        Matrix B = Matrix::I(height());
        while(k > 0) {
            if(k & 1) B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }
    
    Matrix operator+(const Matrix &B) const {
        return (Matrix(*this) += B);
    }
    
    Matrix operator-(const Matrix &B) const {
        return (Matrix(*this) -= B);
    }
    
    Matrix operator*(const Matrix &B) const {
        return (Matrix(*this) *= B);
    }
    
    Matrix operator^(const long long k) const {
        return (Matrix(*this) ^= k);
    }
    
    friend ostream &operator<<(ostream &os, Matrix &p) {
        size_t n = p.height(), m = p.width();
        for(int i = 0; i < n; i++) {
            os << "[";
            for(int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }
    
    
    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for(int i = 0; i < width(); i++) {
            int idx = -1;
            for(int j = i; j < width(); j++) {
                if(B[j][i] != 0) idx = j;
            }
            if(idx == -1) return (0);
            if(i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for(int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for(int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for(int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};

int N, W;
lint K;

vector<int> A;

lint dp[100];

lint jump(int remaining){
    if(remaining == 0){
        return 1;
    }else if(remaining < 0){
        return 0;
    }else if(dp[remaining] != -1){
        return dp[remaining];
    }
    lint ans = 0;
    for(int i = 0; i < N; i++){
        ans += jump(remaining - A[i]);
    }
    return dp[remaining] = ans % mod;
}

int main(){
    cin >> N >> W >> K;
    A.resize(N);
    cins(all(A));
    memset(dp, -1, sizeof(dp));
    
    lint L1 = jump(W), L2 = (jump(W * 2) - L1 * L1 % mod + mod) % mod;
    auto A = Matrix<modint>(2, 2);
    A[0][0] = L1;
    A[0][1] = L2;
    A[1][0] = 1;
    A[1][1] = 0;
    auto x = Matrix<modint>(2, 1);
    x[0][0] = 1;
    x[1][0] = 0;
    A = A ^ K;
    x = A * x;
    cout << x[0][0] << endl;
    
}
0