結果

問題 No.995 タピオカオイシクナーレ
コンテスト
ユーザー ocat
提出日時 2020-02-22 02:10:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,743 bytes
コンパイル時間 1,922 ms
コンパイル使用メモリ 179,428 KB
実行使用メモリ 21,540 KB
最終ジャッジ日時 2024-10-09 11:03:09
合計ジャッジ時間 5,735 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;

class mint {
public:
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    ll get() const { return x; }
    mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; }
    mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); return (t & 1) ? a*a*(*this) : a*a; }
    operator ll () const { return x; }
    operator string () const { return to_string(x); }

    // for prime mod
    mint inv() const { return pow(mod-2); }
    mint& operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};

template<class T>
class Matrix {
public:
    int r, c;
    vector<vector<T>> A;
    Matrix(int r, int c): r(r), c(c) { A.resize(r); for (int i=0; i<r; ++i) A[i].resize(c, 0); }
    Matrix &operator=(const Matrix &B) { tie(A, r, c) = make_tuple(B.A, B.r, B.c); return (*this); }
    const vector<T> &operator[](int i) const { return (A.at(i)); }
    vector<T> &operator[](int i) { return (A.at(i)); }
    Matrix &operator+=(const Matrix &B) { for (int i=0; i<r; ++i) for (int j=0; j<c; ++j) A[i][j] += B[i][j]; return (*this); }
    Matrix &operator-=(const Matrix &B) { for (int i=0; i<r; ++i) for (int j=0; j<c; ++j) A[i][j] -= B[i][j]; return (*this); }
    Matrix &operator*=(T k) { for (int i=0; i<r; ++i) for (int j=0; j<c; ++j) A[i][j] *= k; return (*this); }
    Matrix &operator*=(const Matrix &B) { vector<vector<T>> t(r, vector<T>(B.c, 0)); for (int i=0; i<r; ++i) for (int j=0; j<B.c; ++j) for (int k=0; k<c; ++k) t[i][j] += A[i][k] * B[k][j]; swap(A, t); return (*this); }
    Matrix &operator^=(ll k) { Matrix t(r, r); for (int i=0; i<r; ++i) t[i][i] = 1; for (; k; k>>=1) { if (k & 1) t *= (*this); (*this) *= (*this); } swap(A, t.A); return (*this); }
};

int main() {
    int N, M;
    ll K, _p, _q;
    cin >> N >> M >> K >> _p >> _q;
    mint p(_p), q(_q);

    Matrix<mint> B(N+1, 1);
    ll b;
    for (int i=1; i<=N; ++i) {
        cin >> b;
        B[i][0] = b;
    }

    Matrix<mint> A(1, N+1);
    for (int i=0; i<=M; ++i) A[0][i] = 1;

    Matrix<mint> C(N+1, N+1);
    C[0][0] = 1;
    for (int i=1; i<=N; ++i) {
        C[0][i] = p/q;
        C[i][i] = (q - mint(2) * p) / q;
    }
    C ^= K;
    (A *= C) *= B;
    cout << A[0][0] << endl;

    return 0;
}
0