# 【TopCoder SRM713】CoinsQuery

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 101;

struct Data{
LL val,chs;
inline Data() {val = chs = -1;}
inline Data(LL a, LL b):val(a),chs(b) {}
inline Data operator + (const Data &D) {
if (chs == -1 || D.chs == -1) {
return chs != -1? *this: D;
} else {
Data ret(max(val, D.val), 0);
(ret.chs += (val == ret.val? chs: 0)) %= MOD;
(ret.chs += (D.val == ret.val? D.chs: 0)) %= MOD;
return ret;
}
}
inline Data operator * (const Data &D) {
if (!~chs || !~D.chs) return Data(-1, -1);
return Data(val + D.val, chs * D.chs % MOD);
}
}e(0,1);
struct Matrix{
Data a[N][N]; int x,y;
inline Matrix() {x = y = 0;}
inline Matrix(int X, int Y):x(X),y(Y) {}
inline Matrix operator * (const Matrix &M) {
Matrix ret(M.x, y);
for (int i=1;i<=M.x;i++) {
for (int k=1;k<=x;k++) {
for (int j=1;j<=y;j++) {
ret.a[i][j] = ret.a[i][j] + (a[k][j] * M.a[i][k]);
}
}
}
return ret;
}
}tra[32];

class CoinsQuery {
public:
vector<LL> query(vector<int> w, vector<int> v, vector<int> query) {
int m = query.size(), n = w.size();
tra[0].x = tra[0].y = 100;
for (int i=0;i<n;i++) {
tra[0].a[w[i]][1] = tra[0].a[w[i]][1] + Data(v[i], 1);
}
for (int i=2;i<=100;i++) {
tra[0].a[i-1][i] = e;
}
for (int i=1;i<=30;i++) {
tra[i] = tra[i-1] * tra[i-1];
}

vector<LL> ret;
for (int tt=0;tt<m;tt++) {
Matrix ans(100, 1);
ans.a[1][1] = e;
int cur = query[tt];
for (int i=0;cur;cur>>=1,++i) {
if (cur & 1) {
ans = ans * tra[i];
}
}
ret.push_back(ans.a[1][1].val);
ret.push_back(ans.a[1][1].chs);
}
return ret;
}
private:
};


## 2 thoughts to “【TopCoder SRM713】CoinsQuery”

1. My spouse and i ended up being absolutely delighted that Jordan could conclude his web research from your ideas he gained through the web page. It is now and again perplexing just to possibly be giving for free ideas people today might have been trying to sell. And we all realize we have the writer to appreciate for that. The main explanations you made, the easy website menu, the friendships you will assist to foster – it’s everything extraordinary, and it is helping our son and the family know that that content is cool, and that’s particularly vital. Thank you for all the pieces!

2. Amazing blog! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple adjustements would really make my blog shine. Please let me know where you got your design. Thank you