# 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$.

## 代码

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


418 I'm a teapot