201
edits
Difference between revisions of "BreakFast:2021HDU暑期多校训练营1"
Jump to navigation
Jump to search
→bitset 优化: update D
(→Problem C. Puzzle loop: add C bitset) |
(→bitset 优化: update D) |
||
| Line 379: | Line 379: | ||
return 0; | return 0; | ||
}</syntaxhighlight> | }</syntaxhighlight> | ||
[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop] | |||
== [https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop] == | |||
=== 题目大意 === | |||
<math display="inline">T</math> 组输入，每组给 <math display="inline">n</math> 和 <math display="inline">k</math>. | |||
有 <math display="inline">n</math> 个物品，价值分别为 <math display="inline">a[1], a[2], \cdots, a[n]</math>，每件物品有无穷多件. | |||
求拼凑出总价值为 <math display="inline">k</math> 的方案数. | |||
<math display="inline">1 \leq T \leq 100, 1 \leq n \leq 100, 1 \leq k \leq 10^{18}, 1 \leq a[i] \leq 10</math>. | |||
=== 分析 === | |||
设 <math display="inline">f[i][j]</math> 表示考虑了前 <math display="inline">i</math> 个物品，总价值为 <math display="inline">j</math> 的方案数. | |||
则有状态转移方程 <math display="inline">\begin{aligned} f[i][j] = \sum_{l = 0}^{\lfloor \frac{j}{a[i]} \rfloor}{f[i - 1][j - l \times a[i]]} \end{aligned}</math>. | |||
接下来这一步被题解惊艳到了，拉格朗日插值！！！ | |||
但体会一下也就明白了，还是很妙的感觉. | |||
=== 代码实现 === | |||
<syntaxhighlight lang="cpp">#include <bits/stdc++.h> | |||
using namespace std; | |||
typedef long long ll; | |||
typedef unsigned long long ull; | |||
const int M = (int)1e2; | |||
const int N = (int)5e5; | |||
const double eps = 1e-6; | |||
const int inf = 0x3f3f3f3f; | |||
const ll mod = (ll)1e9 + 7; | |||
int n; ll k; | |||
int a[M + 5]; | |||
int f[N + 5]; | |||
int y[M + 5]; | |||
int pre[M + 5]; | |||
int suf[M + 5]; | |||
int fac[M + 5]; | |||
int inv[M + 5]; | |||
int invfac[M + 5]; | |||
void init() | |||
{ | |||
fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1; | |||
for(int i = 2; i <= M; ++i) | |||
{ | |||
fac[i] = 1ll * fac[i - 1] * i % mod; | |||
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; | |||
invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod; | |||
} | |||
} | |||
int gcd(int a, int b) | |||
{ | |||
return b ? gcd(b, a % b) : a; | |||
} | |||
int Lagrange(int n, ll k) | |||
{ | |||
if(k <= n + 1) return y[k]; | |||
pre[0] = 1; for(int i = 1; i <= n + 1; ++i) pre[i] = (k - i) % mod * pre[i - 1] % mod; | |||
suf[n + 2] = 1; for(int i = n + 1; i >= 1; --i) suf[i] = (k - i) % mod * suf[i + 1] % mod; | |||
int ans = 0, cur; | |||
for(int i = 1; i <= n + 1; ++i) | |||
{ | |||
cur = 1ll * pre[i - 1] * suf[i + 1] % mod * invfac[i - 1] % mod * invfac[n + 1 - i] % mod; | |||
if(n + 1 - i & 1) cur *= -1; | |||
cur = 1ll * cur * y[i] % mod; | |||
ans = (ans + cur) % mod; | |||
} | |||
ans = (ans % mod + mod) % mod; | |||
return ans; | |||
} | |||
void work() | |||
{ | |||
scanf("%d %lld", &n, &k); | |||
int lcm = 1; | |||
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), lcm = lcm / gcd(lcm, a[i]) * a[i]; | |||
memset(f, 0, sizeof(f)); f[0] = 1; | |||
int r = lcm * n; | |||
for(int i = 1; i <= n; ++i) | |||
{ | |||
for(int j = a[i]; j <= r; ++j) f[j] = (f[j] + f[j - a[i]]) % mod; | |||
} | |||
for(int i = k % lcm; i < r; i += lcm) y[i / lcm + 1] = f[i]; | |||
printf("%d\n", Lagrange(n - 1, k / lcm + 1)); | |||
} | |||
int main() | |||
{ | |||
// freopen("input.txt", "r", stdin); | |||
// freopen("output.txt", "w", stdout); | |||
// ios::sync_with_stdio(0); | |||
// cin.tie(0); cout.tie(0); | |||
init(); | |||
int T; scanf("%d", &T); | |||
for(int ca = 1; ca <= T; ++ca) | |||
{ | |||
// printf("Case #%d:\n", ca); | |||
work(); | |||
} | |||
// work(); | |||
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n"; | |||
return 0; | |||
}</syntaxhighlight> | |||
== [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] == | == [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] == | ||