topcoder srm 713 div1

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

problem1 link

如果$a^{b}=c^{d}$，那么一定存在$t,x,y$使得$a=t^{x},c=t^{y}$。一旦$t,x,y$确定，那么可以直接计算出二元组$b,d$有多少。对于$t$，若$t>\sqrt{n}$，那么$x=y=1$。若$t\leq \sqrt{n}$那么$x,y$的值不会超过30，暴力枚举即可

problem2 link

令$f[mask][v]$表示已经遍历了状态$mask$，现在在节点$v$ 时可以遍历到的节点状态。$dp[mask][v]$表示遍历了状态$mask$现在在$v$时遍历完所有节点的方案数，那么有$dp[mask][v]=\sum_{t\in v_{adj}}dp[mask|1<<t][t]*dp[f[mask|1<<t][t]][v]$

problem3 link

设$m$是$w$中的最大值。

设$f[i]$表示重量是$i$的最大价值。那么$f[i]=max(f[i-w_{t}]+v_{t})$.这里还要计算种类的个数，可以定义$\left (value,total \right )$。然后需要重新定义加法和乘法。

由于询问的重量的值很大，可以用矩阵幂来加速。这里的重点是矩阵$M$的$k$次方，只维护连续的$m+1$个重量，即$f[k-m],f[k-(m-1)],..,f[k-2],f[k-1],f[k]$。

所以对于询问$q$来说，只需要计算$M^{q}$即可。这里可以预处理出$M,M^{2},M^{4},M^{8},M^{16}$等以加速运算

$w=(2,3),v=(20,30)$时得到的转移矩阵$M$如下。其中$N$代表无效的转移

$\begin{bmatrix}N & N & N & N\\ (0,1) & N & N &(30,1) \\ N & (0,1) & N & (20,1)\\ N & N & (0,1) &N \end{bmatrix}$

假设计算的$q＝６$,那么初始为$\left (f[-3],f[-2],f[-1],f[0] \right )=\left (N,N,N,(0,1) \right )$，表示重量为0的价值为０，有一种情况

$\left (f[-3],f[-2],f[-1],f[0] \right )*M=\left (f[-2],f[-1],f[0],f[1] \right )=\left (N,N,(0,1),N \right )$，表示重量为0的价值为０，有一种情况

$\left (f[-２],f[-１],f[0],f[1] \right )*M=\left (f[-1],f[0],f[1],f[2] \right )=\left (N,(0,1),N,(20,1) \right )$，表示重量为０的价值为０，有一种情况，重量为２的最大价值为２０，有一种情况

继续下去可以得到：

$\left (f[-１],f[0],f[1],f[2] \right )*M=\left (f[0],f[1],f[2],f[3] \right )=\left ((0,1),N,(20,1) ,(30,1)\right )$

$\left (f[0],f[1],f[2],f[3] \right )*M=\left (f[1],f[2],f[3],f[4] \right )=\left ((0,1),(20,1) ,(30,1),(40,1)\right )$

$\left (f[1],f[2],f[3],f[4] \right )*M=\left (f[2],f[3],f[4],f[5] \right )=\left ((20,1) ,(30,1),(40,1),(50,2)\right )$

$\left (f[2],f[3],f[4],f[5] \right )*M=\left (f[3],f[4],f[5],f[6] \right )=\left ((30,1),(40,1),(50,2),(60,2)\right )$所以重量为６的最大价值为60,有２种情况

code for problem1

#include <cmath>
#include <set>class PowerEquation {
static constexpr int kMod = 1000000007; int Gcd(int x, int y) { return y == 0 ? x : Gcd(y, x % y); } int Get(int x, int y, int n) {
int t = Gcd(x, y);
x /= t;
y /= t;
if (x == y) {
return n;
}
return n / std::max(x, y);
} public:
int count(int n) {
long long result = 1ll * n * n % kMod; int sq = static_cast<int>(std::sqrt(n) + 1); std::set<std::pair<int, int>> S;
for (int t = 2; t * t <= n; ++t) {
long long a = 1;
for (int x = 1; a * t <= n; ++x) {
a *= t;
long long b = 1;
for (int y = 1; b * t <= n; ++y) {
b *= t;
if (S.count({a, b}) > 0) {
continue;
}
S.insert({a, b});
if (a == b && a >= sq) {
result -= n;
}
result += Get(x, y, n);
result %= kMod;
}
}
}
result += 1ll * (n - sq + 1) * n % kMod;
return static_cast<int>(result % kMod);
}
};

code for problem2

#include <string>
#include <vector>class DFSCount {
public:
long long count(const std::vector<std::string> &G) {
int n = static_cast<int>(G.size());
g.resize(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (G[i][j] == 'Y') {
g[i].push_back(j);
}
}
} f.resize(1 << n);
for (int i = 0; i < (1 << n); ++i) {
f[i].resize(n);
}
for (int i = 0; i < (1 << n); ++i) {
for (int j = 0; j < n; ++j) {
if (0 != (i & (1 << j))) {
f[i][j] = Dfs(i, j);
}
}
}
dp.resize(1 << n);
for (int i = 0; i < (1 << n); ++i) {
dp[i].resize(n, -1);
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans += DFS(1 << i, i);
}
return ans;
} private:
int Dfs(int mask, int v) {
if (f[mask][v] != 0) {
return f[mask][v];
}
f[mask][v] = mask;
for (int t : g[v]) {
if (0 == (mask & (1 << t))) {
f[mask][v] |= Dfs(mask | (1 << t), t);
}
}
return f[mask][v];
} long long DFS(int mask, int v) {
if (f[mask][v] == mask) {
return 1;
}
if (dp[mask][v] != -1) {
return dp[mask][v];
}
dp[mask][v] = 0;
for (int t : g[v]) {
if (0 == (mask & (1 << t))) {
int new_mask = mask | (1 << t);
long long x = DFS(new_mask, t);
long long y = DFS(f[new_mask][t], v);
dp[mask][v] += x * y;
}
}
return dp[mask][v];
} std::vector<std::vector<int>> g;
std::vector<std::vector<int>> f;
std::vector<std::vector<long long>> dp;
};

code for problem3

#include <algorithm>
#include <vector>class CoinsQuery {
static constexpr int kMod = 1000000007;
struct Node {
long long value = 0;
long long total = 0; Node() = default;
Node(long long value, long long total) : value(value), total(total) {} bool Valid() const { return value != -1; } Node operator+(const Node &other) const {
if (!Valid()) {
return other;
}
if (!other.Valid()) {
return *this;
}
Node r;
r.value = std::max(value, other.value);
if (value == other.value) {
r.total = (total + other.total) % kMod;
} else if (value > other.value) {
r.total = total;
} else {
r.total = other.total;
}
return r;
} Node operator*(const Node &other) const {
if (!Valid() || !other.Valid()) {
return Node(-1, 0);
}
Node r;
r.value = value + other.value;
r.total = total * other.total % kMod;
return r;
}
}; struct Matrix {
int n = 0;
int m = 0;
std::vector<std::vector<Node>> mat;
Matrix(int n = 0, int m = 0) : n(n), m(m) {
mat.resize(n);
for (int i = 0; i < n; ++i) {
mat[i].resize(m);
for (int j = 0; j < m; ++j) {
mat[i][j].value = -1;
mat[i][j].total = 0;
}
}
} Matrix operator*(const Matrix &other) const {
int n = this->n;
int m = this->m;
int r = other.m;
Matrix result(n, r);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < r; ++j) {
for (int k = 0; k < m; ++k) {
result.mat[i][j] = result.mat[i][j] + mat[i][k] * other.mat[k][j];
}
}
}
return result;
}
}; public:
std::vector<long long> query(const std::vector<int> &w,
const std::vector<int> &v,
const std::vector<int> &query) {
int n = static_cast<int>(w.size());
constexpr int kMax = 30;
std::vector<Matrix> all(kMax);
int m = *std::max_element(w.begin(), w.end());
all[0] = Matrix(m + 1, m + 1);
for (int i = 0; i < n; ++i) {
all[0].mat[m - w[i] + 1][m] = all[0].mat[m - w[i] + 1][m] + Node(v[i], 1);
} for (int i = 0; i < m; ++i) {
all[0].mat[i + 1][i] = all[0].mat[i + 1][i] + Node(0, 1);
} for (int i = 1; i < kMax; ++i) {
all[i] = all[i - 1] * all[i - 1];
}
std::vector<long long> result;
for (int q : query) {
Matrix i(1, m + 1);
i.mat[0][m] = Node(0, 1);
for (int j = 0; j < kMax; ++j) {
if ((q & (1 << j)) != 0) {
i = i * all[j];
}
}
if (!i.mat[0][m].Valid()) {
result.push_back(-1);
result.push_back(-1);
} else {
result.push_back(i.mat[0][m].value);
result.push_back(i.mat[0][m].total);
}
}
return result;
}
};