結果
問題 | No.995 タピオカオイシクナーレ |
ユーザー | tomoron13 |
提出日時 | 2020-06-05 13:27:58 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 7,855 bytes |
コンパイル時間 | 1,556 ms |
コンパイル使用メモリ | 117,884 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-09 00:21:40 |
合計ジャッジ時間 | 2,816 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 2 ms
5,376 KB |
testcase_04 | AC | 2 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 | 1 ms
5,376 KB |
testcase_10 | AC | 1 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 | 1 ms
5,376 KB |
testcase_16 | AC | 15 ms
5,376 KB |
testcase_17 | AC | 15 ms
5,376 KB |
testcase_18 | AC | 15 ms
5,376 KB |
testcase_19 | AC | 15 ms
5,376 KB |
testcase_20 | AC | 15 ms
5,376 KB |
testcase_21 | AC | 15 ms
5,376 KB |
testcase_22 | AC | 15 ms
5,376 KB |
testcase_23 | AC | 14 ms
5,376 KB |
testcase_24 | AC | 14 ms
5,376 KB |
testcase_25 | AC | 15 ms
5,376 KB |
ソースコード
#include <stdio.h> #include <algorithm> #include <assert.h> #include <cmath> #include <deque> #include <iostream> #include <limits.h> #include<functional> #include <map> #include <math.h> #include <queue> #include <set> #include <stdlib.h> #include <string.h> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #include <stack> #include <deque> #include <tuple> #include <float.h> #include<time.h> #define LL long long #define pii pair<int,int> #define pLL pair<LL,LL> #define mp make_pair #define mt make_tuple #define pq priority_queue<LL> #define pqg priority_queue<LL,vector<LL>,greater<LL>> #define pb push_back #define vecLL vector<LL> #define vecpii vector<pii> #define vecpLL vector<pLL> #define vecbL vector<bool> #define mat vector<vecLL> #define endl "\n" #define REP(e,v) for(auto e:v) #define rep(i, a, n) for(LL i = a; i < n;i++) #define Arep(i, a, n) for(i = a; i < n;i++) #define MOD 1000000007 #define INF LLONG_MAX/2 #define DINF DBL_MAX/2 using namespace std; /*↓マイライブラリ↓*/ //clock_t start = clock(); // //clock_t end = clock(); // //const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0; //printf("time %lf[ms]\n", time); LL linp(){ LL x; scanf("%lld",&x); return x; } LL mod(LL i){ LL mi = i % MOD; if(mi < 0) mi += MOD; return mi; } mat mul(const mat &A,const mat &B){ mat C(A.size(),vecLL(B[0].size())); if(A[0].size() != B.size()){ cout << "エラー:掛け算不可" << endl; exit(0); } rep(i,0,A.size()){ rep(j,0,B[0].size()){ rep(k,0,B.size()){ C[i][j] = mod(C[i][j] + A[i][k]*B[k][j]); } } } return C; } mat matpow(const mat &A,LL n){ if(n == 1) return A; mat A_2 = matpow(A,n/2); A_2 = mul(A_2,A_2); if(n % 2 == 0){ return A_2; }else{ return mul(A,A_2); } } vecLL bit(LL i,LL N){ vecLL biti(N); rep(x,0,N){ biti[N - 1 - x] = (i >> x) & 1; } return biti; } void swap(LL &a, LL &b){ LL t = a; a = b; b = t; return ; } LL digit(LL x,LL n){ LL count = 1; while(x >= n){ x = x/n; count++; } return count; } LL gcd(LL i,LL j){ if(j != 0) return gcd(j, i % j); else return i; } pLL extgcd(LL a,LL m){//ax+my = 1の解 pLL ans; if(m != 0){ pLL next = extgcd(m,a%m); ans.first = next.second; ans.second = next.first-(a/m)*next.second; } else{ ans = pLL(1,0); } return ans; } LL div(LL a, LL b,LL m){ return mod(mod(a) * mod(extgcd(b,m).first)); } LL numperm(LL x,LL y){ LL res = 1; for(LL i = x; i >= y; i--){ res = mod(res * mod(i)); } return mod(res); } LL pow(LL x,LL y){ x = mod(x); if(y == 1){ return mod(x); } LL res = mod(pow(mod(x*x),y/2)); if(y % 2 == 0){ return res; } else{ return mod(x*res); } } bool isPrime(LL X){ rep(i,2,(LL)(sqrt(X)+1)){ if(X % i == 0){ return false; } } return true; } vecLL Eratosthenes(LL n){//素数のベクトルを返す bool isPrime[n]; fill(isPrime,isPrime+n,true); isPrime[0] = isPrime[1] = false; rep(i,2,sqrt(n)+1){ if(isPrime[i]){ for(LL j = 2*i ;j <= n ; j += i){ isPrime[j] = false; } } } vecLL P; rep(i,2,n+1){ if(isPrime[i]){ P.push_back(i); } } return P; } map<LL,LL> factalization(LL N){ map<LL,LL> fac; LL oriN = N; LL div = 1; for(LL i = 2;i*i <= N;++i){ while(N%i == 0){ fac[i]++; div *= i; N /= i; } } if(oriN/div != 1){ fac[oriN/div]++; } return fac; } struct edge {//枝 LL to,cost; double dcost;//コストが整数でない場合に使う } ; struct vertex{//頂点(枝付き) LL key; double dkey;//キーが整数でない場合に使う vector<edge> edges;//頂点から伸びる枝 }; class Graph{ public: LL V;//頂点数 vertex* vertices;//グラフ Graph(LL v){//頂点数を指定してグラフの初期化 V = v;//頂点数 vertices = new vertex[V];//頂点集合 rep(i,0,V){ vertices[i].key = -1;//キー初期値は-1 vertices[i].dkey = -1;//キー初期値は-1 } } void setDE(LL i,LL j,LL cos){//i→jにコストcosの有向枝を加える edge e; e.to= j; e.cost = cos; vertices[i].edges.push_back(e); return; } void setDE(LL i,LL j,double dcos){//i→jにコストcosの有向枝を加える edge e; e.to= j; e.dcost = dcos; vertices[i].edges.push_back(e); return; } void setUDE(LL i,LL j,LL cos){//(i,j)にコストcosの無向枝を加える edge ei,ej; ei.to = j; ej.to = i; ei.cost = ej.cost = cos; vertices[i].edges.push_back(ei); vertices[j].edges.push_back(ej); return; } void setUDE(LL i,LL j,double dcos){//(i,j)にコストcosの無向枝を加える edge ei,ej; ei.to = j; ej.to = i; ei.dcost = ej.dcost = dcos; vertices[i].edges.push_back(ei); vertices[j].edges.push_back(ej); return; } void setKey(LL i,LL newKey){//キー変更 vertices[i].key = newKey; } void setKey(LL i,double newKey){//キー変更 vertices[i].key = newKey; } edge getEdge(LL i,LL j){ rep(a,0,vertices[i].edges.size()){ if(vertices[i].edges[a].to == j){ return vertices[i].edges[a]; } } return (edge){j,INF,DINF};//なければ,コストINFの枝を返す } void bellman_ford(LL s,LL b[]){ fill(b,b+V,INF); b[s] = 0; while(true){ bool update = false; rep(i,0,V){ rep(j,0,vertices[i].edges.size()){ edge e = vertices[i].edges[j]; if(b[e.to] > b[i] + e.cost){ b[e.to] = b[i] + e.cost; update = true; } } } if(!update) break; } return; } void dijkstra(LL s, LL d[]) {//ダイクストラ(始点を入力とし、各点への最小距離を返す) priority_queue<pLL, vector<pLL>, greater<pLL> > que; fill(d,d+V,INF); d[s] = 0; que.push(pLL(0, s)); while (!que.empty()) { pLL p = que.top(); que.pop(); LL v = p.second; if (d[v] < p.first) continue; rep(i,0, vertices[v].edges.size()) { edge e = vertices[v].edges[i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(pLL(d[e.to], e.to)); } } } return; } void warshall_floyd(LL **w){ rep(i,0,V){ rep(j,0,V){ w[i][j] = INF; } } rep(i,0,V){ rep(j,0,vertices[i].edges.size()){ w[i][vertices[i].edges[j].to] = vertices[i].edges[j].cost; } } rep(i,0,V){ w[i][i] = 0; } rep(i,0,V){ rep(j,0,V){ rep(k,0,V){ w[i][j] = min(w[i][j],w[i][k]+w[k][j]); } } } } }; class UF { public: LL N; LL* par; LL* rank; UF(LL n){ N = n; par = new LL[N]; rank = new LL[N]; rep(i,0,N){ par[i] = i; rank[i] = i; } return; } LL root(LL x){ if(x == par[x]) return x; else return par[x] = root(par[x]); } bool same(LL x,LL y){ return (root(x) == root(y)); } void Union(LL x,LL y){ LL rtx = root(x); LL rty = root(y); if(rank[rtx] < rank[rty]){ par[rtx] = rty; } else{ par[rty] = rtx; if(rank[rtx] == rank[rty]){ rank[rtx]++; } } } }; class ST{ }; /*↑マイライブラリ↑*/ LL solveA(){ return 0; } LL solveB(){ return 0; } LL solveC(){ LL N,M,K,p,q; cin >> N >> M >> K >> p >> q; mat A(2,vecLL(2)); LL P = p*extgcd(q,MOD).first%MOD; A[0][0] = mod(1 - P);A[0][1] = mod(P); A[1][0] = mod(P) ;A[1][1] = mod(1 - P); mat A_k = matpow(A,K); LL tapin = 0; LL tapout = 0; rep(i,0,N){ LL x = linp(); if(i < M){ tapin = mod(tapin + x); }else{ tapout = mod(tapout + x); } } cout << mod(mod(tapin*A_k[0][0]) + mod(tapout*A_k[1][0])) << endl; return 0; } LL solveD(){ return 0; } LL solveE(){ return 0; } signed main(){ //solveA(); //solveB(); solveC(); //solveD(); //solveE(); return 0; }