经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
BZOJ4011: [HNOI2015]落忆枫音(dp 乘法原理)
来源:cnblogs  作者:自为风月马前卒  时间:2018/11/30 9:38:49  对本文有异议

题意

题目链接

Sol

非常妙的一道题

\(inder[i]\)表示\(i\)号节点的度数

首先如果是个DAG的话,可以考虑在每个点的入边中选一条边作为树形图上的边,这样\(ans = \prod_{i > 1} inder[i]\)

如果加入一条边的话,算答案的时候可能会把一些环的贡献也算进去(比如样例中\(2 - 4 - 3\))这个环

考虑减去环上的贡献,注意形成的环不止一个,准确的来说,如果加入了\(x -> y\)这条边,那么在原图中所有\(y -> x\)的路径都应该计算贡献

其中一条路径的贡献为\(\frac{ans}{S \in (y -> x) inder[S]}\)

dp一遍求出所有贡献即可

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1e6 + 10, mod = 1e9 + 7;
  4. inline int read() {
  5. char c = getchar(); int x = 0, f = 1;
  6. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  7. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  8. return x * f;
  9. }
  10. int N, M, X, Y, inder[MAXN], inv[MAXN], t[MAXN], f[MAXN];
  11. vector<int> v[MAXN];
  12. void add(int &x, int y) {
  13. if(x + y < 0) x = x + y + mod;
  14. else x = (x + y >= mod ? x + y - mod : x + y);
  15. }
  16. int mul(int x, int y) {
  17. return 1ll * x * y % mod;
  18. }
  19. void Topsort() {
  20. queue<int> q;
  21. for(int i = 1; i <= N; i++) if(!inder[i]) q.push(i);
  22. while(!q.empty()) {
  23. int p = q.front(); q.pop(); f[p] = mul(f[p], inv[t[p]]);
  24. for(int i = 0; i < v[p].size(); i++) {
  25. int to = v[p][i];
  26. add(f[to], f[p]);
  27. if(!(--inder[to])) q.push(to);
  28. }
  29. }
  30. }
  31. int main() {
  32. N = read(); M = read(); X = read(); Y = read();
  33. inv[1] = 1; for(int i = 2; i <= M + 1; i++) inv[i] = mul((mod - mod / i), inv[mod % i]);
  34. for(int i = 1; i <= M; i++) {
  35. int x = read(), y = read();
  36. v[x].push_back(y); inder[y]++;
  37. }
  38. int ans = 1; inder[Y]++;
  39. for(int i = 2; i <= N; i++) ans = mul(ans, inder[i]);
  40. if(Y == 1) {cout << ans; return 0;}
  41. memcpy(t, inder, sizeof(inder));
  42. inder[Y]--;
  43. f[Y] = ans; Topsort();
  44. cout << (ans - f[X] + mod) % mod;
  45. return 0;
  46. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号