UVA 11174 Stand in a Line——组合数+取模

UVA 11174 Stand in a Line——组合数+取模

要求（b / c） % mod,

令a = b / c;则a % mod = b * (c ^ (mod - 2)) % mod;

#include #include #include #include #include using namespace std;const long long mod = 1000000007;const int maxn = 400005;int T, n, m, tot, head[maxn], num[maxn], fa[maxn];long long f[maxn];struct Edge { int to, next;}edge[maxn<<1];void init() { tot = 0; memset(head, -1, sizeof(head));}void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}void dfs(int u, int p) { for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v == p) continue; dfs(v, u); num[u] += num[v]; }}long long mpow(long long x, long long y) { long long ans = 1; while (y) { if (y & 1) ans = ans * x % mod; x = x * x % mod; y >>= 1; } return ans;}int main() { f[0] = 1; for (int i = 1; i < maxn; i++) { f[i] = (f[i-1] * i) % mod; } scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &n, &m); init(); num[0] = 0; for (int i = 1; i <= n; i++) num[i] = 1; memset(fa, -1, sizeof(fa)); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); fa[u] = v; addedge(v, u); } for (int i = 1; i <= n; i++) { if (fa[i] == -1) addedge(0, i); } dfs(0, -1); long long ans = 1; for (int i = 1; i <= n; i++) { ans = (ans * num[i]) % mod; } ans = (f[n] * mpow(ans, mod-2)) % mod; printf("%lld\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。