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;
}