题目大意
有 \(N\) 种硬币，两种硬币的面值可能相同。给定 \(q\) 个限制，第 \(i\) 个限制由 \(b_i\) 和 \(c_i\) 组成，表示第 \(b_i\) 种硬币的数量严格大于第 \(c_i\) 种硬币的数量，且每个 \(b_i\) 与 \(c_i\) 都是唯一的。问在满足所有限制的情况下，有多少种可能的方案，能组成正好等于 \(t\) 的总面值，并将方案数对 \(10^9 + 7\) 取模。
题意分析
不难看出，这题里的限制具有方向性，我们将每条限制看作一条从 \(c_i\) 指向 $ b_i$ 的有向边，此时如果出现了环，则限制一定不成立，故方案数为 \(0\) ; 否则，我们就可以将所有限制画成一个有向无环图。由于每个 \(b_i\) 与 \(c_i\) 都是唯一的，故每个节点的入度和出度都为 \(1\) ，即这个有向无环图一定是一条链，从这条链的头部开始，每个节点的后继币种的数量一定严格大于当前节点。
此时我们发现，如果一条链的某个节点被选了 \(i\) 次，它的后继节点则至少被选择 \(i + 1\) 次才能满足限制条件，因为一种硬币最少选 \(0\) 次，所以在符合限制的情况下，一条链的头部节点最少选 \(0\) 次，一号节点最少选 \(1\) 次，二号节点最少选 \(2\) 次，以此类推。故这些硬币无论方案最终如何，是必须要至少选这些次数的，我们就可以将它们从 \(t\) 中剔除。而在当前情况下，因为所有硬币都已经最少，且必须保持严格上升，所以更新链上的其中一个节点时，它的所有后继节点都必须要相应更新。但是题目没有要求我们求出方案本身，只要求输出方案数，我们便可以视为我们在更新时，更新了一枚币值等于当前节点以及它的所有后继的总币值的硬币。此时便解决了后效性问题，可以用完全背包求解。
AC代码
#include <bits/stdc++.h>
#define N 100050
#define int long long //不开 long long 见祖宗
#define mod (1000000007LL)
using namespace std;
int t, n, q;
int a[350], pre[N], f[N], son[N], head[350], vis[350], b[350];
int sum, tmp;
int find(int x){ //找链的头部
if(pre[x] == 0) return head[x] = x;
return head[x] = find(pre[x]);
}
signed main(){
cin >> n >> q >> t;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) head[i] = i;
for(int i = 1; i <= q; i++){
int x, y;
cin >> x >> y;
if(find(x) == find(y)){cout << 0; return 0;} //并查集判断环
pre[x] = y; son[y] = x;
}
for(int i = 1; i <= n; i++) find(i);
for(int i = 1; i <= n; i++) if(son[i] == 0) {
for(int j = i; j != 0; j = pre[j]) tmp++;
for(int j = i; j != 0 && tmp >= 0; j = pre[j])
sum += --tmp * a[j],
b[j] = a[j] + b[son[j]];
t -= sum, tmp = 0, sum = 0;
if(t < 0){cout << 0; return 0;} //在满足限制的最少情况下就已经超过t，一定没有可行解
}
f[0] = 1;
for(int i = 1; i <= n; i++)
for(int v = 0; v + b[i] <= t; v++)
f[v + b[i]] = (f[v + b[i]] % mod + f[v] % mod) % mod; //好事多模
cout << f[t] % mod;
return 0;
}