网站建设验收汇报,移动关闭流量自动续费,做淘宝要网站?,赣州招聘网依然是liurujia计数练习题。依然是自己想没想出来#xff0c;在MOD是素数的情况下除以x即为乘x的逆。这个真心以前没听过#xff0c;用了这个方法后处理就变得十分巧妙。 整个程序步骤还是很清晰的#xff0c;先上来算阶乘与逆#xff08;求数的逆还是有点没理解透#xf…依然是liurujia计数练习题。依然是自己想没想出来在MOD是素数的情况下除以x即为乘x的逆。这个真心以前没听过用了这个方法后处理就变得十分巧妙。 整个程序步骤还是很清晰的先上来算阶乘与逆求数的逆还是有点没理解透需要后续章节继续学习。然后读入建图只能用邻接表了注意加上最开始的那个根节点就行了。 然后就是搜索按照书上的公式计算就行了。 代码如下 1 #include iostream2 #include cstdio3 #include cstring4 #include vector5 #include cmath6 #include algorithm7 #define LEN 401008 #define MOD 10000000079 #define ll long long
10 using namespace std;
11
12 int n, m, isrt[LEN];
13 ll jc[LEN], rjc[LEN], ans;
14 vectorll map[LEN];
15
16 //扩展欧几里德
17 ll extend_gcd(ll a, ll b, ll x,ll y){
18 ll t,_m;
19 if ((b0)(a0)) return -1;//表示无最大公因数
20 if (b0){
21 x1;y0; return a;
22 }
23 else {
24 _mextend_gcd(b,a % b,x,y);
25 tx;xy;yt-(a/b)*y;
26 }
27 return _m;
28 }
29
30 //初始化阶乘和他的逆
31 void cntjc()
32 {
33 ll x,y;
34 jc[0] 1;
35 for(int i1; iLEN; i){
36 jc[i] (jc[i-1]*i)%MOD;
37 ll ta extend_gcd(i,MOD,x,y);
38 if(ta1 || ta-1) rjc[i] (xMOD)%MOD;
39 else rjc[i] -1;
40 }
41 }
42
43 void init()
44 {
45 memset(isrt, 0, sizeof isrt);
46 for(int i0; iLEN; i){
47 map[i].clear();
48 }
49 //建图
50 int a, b;
51 scanf(%d%d, n, m);
52 for(int i0; im; i){
53 scanf(%d%d, a, b);
54 map[b].push_back(a);
55 isrt[a] 1;
56 }
57 //加入总的根节点
58 for(int i1; in; i){
59 if(!isrt[i]) map[0].push_back(i);
60 }
61 }
62
63 int DFS(int vex)
64 {
65 int cnt 1;
66 for(vectorll::iterator itmap[vex].begin(); it!map[vex].end(); it){
67 cntDFS(*it);
68 }
69 if(vex) ans ans*rjc[cnt]%MOD;
70 return cnt;
71 }
72
73 int main()
74 {
75 // freopen(in.txt, r, stdin);
76
77 int T;
78 scanf(%d, T);
79 cntjc();
80 while(T--)
81 {
82 init();
83 ans jc[n];
84 DFS(0);
85 printf(%lld\n, ans);
86 }
87 return 0;
88 } View Code 转载于:https://www.cnblogs.com/shu-xiaohao/p/3413540.html
