結果
問題 | No.995 タピオカオイシクナーレ |
ユーザー |
![]() |
提出日時 | 2020-02-22 18:21:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 2,144 bytes |
コンパイル時間 | 883 ms |
コンパイル使用メモリ | 98,256 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-09 20:38:40 |
合計ジャッジ時間 | 1,958 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
/* -*- coding: utf-8 -*- * * 995.cc: No.995 タピオカオイシクナーレ - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100000; const int MOD = 1000000007; /* typedef */ typedef long long ll; typedef int vec[2]; typedef vec mat[2]; /* global variables */ int bs[MAX_N]; mat ma, mb, mc; /* subroutines */ inline void initmat(mat a) { memset(a, 0, sizeof(mat)); } inline void unitmat(mat a) { initmat(a); a[0][0] = a[1][1] = 1; } inline void copymat(const mat a, mat b) { memcpy(b, a, sizeof(mat)); } inline void mulmat(const mat a, const mat b, mat c) { c[0][0] = ((ll)a[0][0] * b[0][0] % MOD + (ll)a[0][1] * b[1][0] % MOD) % MOD; c[0][1] = ((ll)a[0][0] * b[0][1] % MOD + (ll)a[0][1] * b[1][1] % MOD) % MOD; c[1][0] = ((ll)a[1][0] * b[0][0] % MOD + (ll)a[1][1] * b[1][0] % MOD) % MOD; c[1][1] = ((ll)a[1][0] * b[0][1] % MOD + (ll)a[1][1] * b[1][1] % MOD) % MOD; } inline void powmat(const mat a, ll b, mat c) { mat s, t; copymat(a, s); unitmat(c); while (b > 0) { if (b & 1) { mulmat(c, s, t); copymat(t, c); } mulmat(s, s, t); copymat(t, s); b >>= 1; } } int powmod(int a, ll n) { // a^n % MOD int pm = 1; while (n > 0) { if (n & 1) pm = (ll)pm * a % MOD; a = (ll)a * a % MOD; n >>= 1; } return pm; } /* main */ int main() { int n, m, p, q; ll k; scanf("%d%d%lld%d%d", &n, &m, &k, &p, &q); for (int i = 0; i < n; i++) scanf("%d", bs + i); int iq = powmod(q, MOD - 2); int p0 = (ll)(q - p) * iq % MOD, p1 = (ll)p * iq % MOD; ma[0][0] = p0; ma[0][1] = p1; ma[1][0] = p1; ma[1][1] = p0; powmat(ma, k, mb); int pk0 = mb[0][0], pk1 = mb[1][0]; int esum = 0; for (int i = 0; i < n; i++) esum = (esum + (ll)bs[i] * ((i < m) ? pk0 : pk1) % MOD) % MOD; printf("%d\n", esum); return 0; }