相关链接
题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14572&rd=16882
题目大意
给$n(n \le 100)$类物品,第$i$类物品重量为$w_i(w_i \le 100)$,价值为$v_i(v_i \le 10^9)$,数量无限
给定$m(m \le 100)$个询问,第$i$询问请你回答总重量恰好为$q_i(q_i \le 10^9)$的物品,价值和最大为多少
你还需要求出使价值最大的方案数是多少(同类物品视作一样,摆放顺序不同算不同)
解题报告
规定每个物品重量不超过$100$那么我们就可以矩乘
但有一个问题:我们不仅要让价值最大,还要求方案数
但类比倍增Floyd:在一定条件,矩乘重载运算符之后仍然满足结合律
比如说这个题,我们可以:
重载加法为:两种方案取最优
重载乘法为:将两种方案拼起来(方案数相乘,价值相加)
然后直接做是$O(m n^3 \log n)$的,会在第$21$个点$TLE$
于是我们预处理转移矩阵的幂次,然后对于每个询问就是向量与矩阵相乘,单次复杂度是$O(n^2)$的
于是总的时间复杂度优化到:$O(m n^2 \log n + n^3 \log n)$
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: };