結果

問題 No.995 タピオカオイシクナーレ
コンテスト
ユーザー graythunder1
提出日時 2020-02-22 02:51:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 1,603 bytes
コンパイル時間 2,013 ms
コンパイル使用メモリ 160,760 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-09 13:35:02
合計ジャッジ時間 3,488 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<vector<ll,ll>> mat;

#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define rrep(i,a) for(ll i=a-1;i>=0;i--)
#define MOD 1000000007

//debug
#define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

void copy(ll* A, ll* B){
  rep(i, 4) B[i] = A[i];
}

void matmul(ll* A, ll* B, ll* AB){
  AB[0] = (A[0] * B[0] + A[1] * B[2] + MOD) % MOD;
  AB[1] = (A[0] * B[1] + A[1] * B[3] + MOD) % MOD;
  AB[2] = (A[2] * B[0] + A[3] * B[2] + MOD) % MOD;
  AB[3] = (A[2] * B[1] + A[3] * B[3] + MOD) % MOD;
}

void matpow(ll* A, ll k, ll* res){
  ll pow[4], tmp[4];
  rep(i, 4) res[i] = (i == 0) || (i == 3);
  rep(i, 4) pow[i] = A[i];
  while(k > 0){
    if(k % 2) {
      matmul(res, pow, tmp);
      copy(tmp, res);
    }
    matmul(pow, pow, tmp);
    copy(tmp, pow);
    k /= 2;
  }
}

int main(){
  ll N, M, K, p, q;
  cin >> N >> M >> K >> p >> q;
  ll b[N];
  rep(i, N) cin >> b[i];

  ll bsum = 0, b_in = 0;
  rep(i, N) bsum = (bsum + b[i]) % MOD;
  rep(i, M) b_in = (b_in + b[i]) % MOD;

  ll r = p * modinv(q, MOD) % MOD;
  ll E00 = (1 - 2 * r + MOD) % MOD;
  ll E01 = r * bsum % MOD;
  ll E[] = {E00, E01, 0, 1};
  ll E_K[4];
  matpow(E, K, E_K);
  ll R = (E_K[0] * b_in + E_K[1]) % MOD;

  cout << R << endl;

  return 0;
}
0