依然是liurujia計(jì)數(shù)練習(xí)題。依然是自己想沒想出來(lái)，在MOD是素?cái)?shù)的情況下除以x即為乘x的逆。這個(gè)真心以前沒聽過(guò)，用了這個(gè)方法后處理就變得十分巧妙。

整個(gè)程序步驟還是很清晰的，先上來(lái)算階乘與逆（求數(shù)的逆還是有點(diǎn)沒理解透，需要后續(xù)章節(jié)繼續(xù)學(xué)習(xí)）。然后讀入建圖只能用鄰接表了，注意加上最開始的那個(gè)根節(jié)點(diǎn)就行了。

然后就是搜索按照書上的公式計(jì)算就行了。

代碼如下：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <cmath> 6 #include <algorithm> 7 #define LEN 40100 8 #define MOD 1000000007 9 #define ll long long 10 using namespace std; 11 12 int n, m, isrt[LEN]; 13 ll jc[LEN], rjc[LEN], ans; 14 vector<ll> map[LEN]; 15 16 //擴(kuò)展歐幾里德 17 ll extend_gcd(ll a, ll b, ll &x,ll &y){ 18 ll t,_m; 19 if ((b==0)&(a==0)) return -1;//表示無(wú)最大公因數(shù) 20 if (b==0){ 21 x=1;y=0; return a; 22 } 23 else { 24 _m=extend_gcd(b,a % b,x,y); 25 t=x;x=y;y=t-(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 i=1; i<LEN; i++){ 36 jc[i] = (jc[i-1]*i)%MOD; 37 ll ta = extend_gcd(i,MOD,x,y); 38 if(ta==1 || ta==-1) rjc[i] = (x+MOD)%MOD; 39 else rjc[i] = -1; 40 } 41 } 42 43 void init() 44 { 45 memset(isrt, 0, sizeof isrt); 46 for(int i=0; i<LEN; i++){ 47 map[i].clear(); 48 } 49 //建圖 50 int a, b; 51 scanf("%d%d", &n, &m); 52 for(int i=0; i<m; i++){ 53 scanf("%d%d", &a, &b); 54 map[b].push_back(a); 55 isrt[a] = 1; 56 } 57 //加入總的根節(jié)點(diǎn) 58 for(int i=1; i<=n; 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(vector<ll>::iterator it=map[vex].begin(); it!=map[vex].end(); ++it){ 67 cnt+=DFS(*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

?

轉(zhuǎn)載于:https://www.cnblogs.com/shu-xiaohao/p/3413540.html

總結(jié)

以上是生活随笔為你收集整理的uva 11174(排列组合+搜索)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。