Coin Troubles

题目描述

In the Isle of Guernsey there are $n$ different types of coins. For each $i \; (1 \le i \le n)$, coin of type $i$ is worth $a_i$ cents. It is possible that $a_i=a_j$ for some $i$ and $j \; (i \neq j)$.
Bessie has some set of these coins totaling $t$ cents. She tells Jessie $q$ pairs of integers. For each $i \; (1 \le i \le q)$, the pair $b_i, c_i$ tells Jessie that Bessie has a strictly greater number of coins of type $b_i$ than coins of type $c_i$. It is known that all $b_i$ are distinct and all $c_i$ are distinct.
Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some $i \; (1 \le i \le n)$, such that the number of coins Bessie has of type $i$ is different in the two combinations. Since the answer can be very large, output it modulo $1000000007$ ($10^9+7$).
If there are no possible combinations of coins totaling $t$ cents that satisfy Bessie’s conditions, output $0$.

题意概述

你有$n$种纸币,第$i$种纸币的价值为$a_i$(可能有多个$a_i$相等)。已知所有纸币的总价值为$t$。给定$q$对整数$b_i, c_i$,表示第$b_i$种纸币的数量严格大于第$c_i$种纸币的数量。所有$b_i$均不相等,所有$c_i$均不相等。求满足这些条件的方案数。
数据范围:$1 \le n \le 300, \; 1 \le t \le 10^5, \; 1 \le a_i \le 10^5$。

算法分析

将每种硬币看成点,每条限制看成有向边,这样就构成了一张有向图。若这张图中存在环,则方案数为$0$。否则,所有边构成的一定是链。对于一条链上的点$v_1, v_2, \ldots, v_m$,我们将$a_{v_2}$变成$a_{v_1}+a_{v_2}$,将$a_{v_3}$变成$a_{v_1}+a_{v_2}+a_{v_3}$,以此类推。这样做的原因是:如果选了第$v_2$件物品一次,就必须也选第$v_1$件物品一次;如果选了第$v_3$件物品一次,就必须也选第$v_1$和第$v_2$件物品一次。这就变成一个完全背包问题了。注意到完全背包问题中的物品是可以不选的,而在这个问题中有些物品是必须选的。例如,第$v_{m-1}$件物品必须至少选一次,第$v_{m-2}$件物品必须至少选两次(因为题目中要求严格大于)。只需在$t$中减去这些必须选的就可以了。

代码

#include <iostream>
using namespace std;
const long long mod = 1000000007ll;
long long n, q, t, ma, a[301], to[301], f[100001];
bool m[301], in[301], vis[301];
void dfs(long long u, long long d, long long s) {
  ma = d, vis[u] = true;
  if (to[u]) dfs(to[u], d + 1, s + a[u]);
  t -= (ma - d) * a[u], a[u] += s;
}
int main()
{
  cin >> n >> q >> t, f[0] = 1;
  for (int i = 1; i <= n; cin >> a[i], ++i);
  for (int i = 1; i <= q; ++i) {
    long long b, c; cin >> b >> c;
    m[b] = m[c] = true, in[c] = true, to[b] = c;
  }
  for (int i = 1; i <= n; ++i)
    if (m[i] && !in[i]) ma = 0, dfs(i, 0, 0);
  if (t < 0) { cout << 0 << endl; return 0; }
  for (int i = 1; i <= n; ++i)
    if (m[i] && !vis[i]) { cout << 0 << endl; return 0; }
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= t - a[i]; ++j)
      (f[j + a[i]] += f[j]) %= mod;
  cout << f[t] << endl;
  return 0;
}

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *