『壹』 ACM 演算法超難題目
出題人的表達能力太差，題目敘述得很糟糕，最後兩個例子也錯了
比較好的敘述是，輸入n，輸出從0到32中取6項按字典序排序下的第n個組合（從第0個組合0,1,2,3,4,5開始計）
這種談不上什麼難題，只不過是入門級的問題
在給定前k項的（記第k項為m）情況下餘下的項共有C(32-m,6-k)種情況，這里C(x,y)表示x取y的組合數，以此編程即可
給你一個例子
#include<stdio.h>
intbinom(intn,intm)
{
inti,c=1;
if(2*m>n)
n=n-m;
for(i=1;i<=m;i++)
c=c*(n+1-i)/i;
returnc;
}
intmain()
{
inti,n;
intA[6]={-1};
while(scanf("%d",&n)!=EOF)
{
n++;
if(n<=0||n>binom(33,6))
{
printf("Invalidinput ");
continue;
}
for(i=1;i<=5;i++)
{
for(A[i]=A[i-1]+1;;A[i]++)
{
intt=binom(32-A[i],6-i);
if(n>t)
n-=t;
else
break;
}
printf("%d,",A[i]);
}
printf("%d ",A[i-1]+n);
}
return0;
}
『貳』 怎樣求大組合數（取模）（ACM演算法）
這種題目然做過的，
意思比較簡單，就由 m 個共 0 和 n 個 1 組成一個串，但從左到右要1出現的次數不少於0出現的次數。
由大牛的演算法： 結果就是 C(m+n, n) - C(m+n, m-1) 再取模，我們可以對式子化簡一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由於組合數很大，直接用大數乘除就會超時了，看了別人的報告才知道原來可以用素數化簡快速求模的， n! = 2^p[i] *
3^p[i] * 5^p[i]*...... 再求模就可以很快了~(^ = ^)~。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime 記錄素數， p 記錄素數的冪 len 記錄長度
void getprime() // 篩法找素數
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
if( !sig[i] )
{
prime[k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // K! 的素數分解, S為指數的加減(分母，分子)
{
int i, mid;
for(i=0; prime[i]<=k && prime[i]; i++)
{
mid = k;
while(mid)
{
if(s)
p[i] += mid/prime[i];
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i)
len = i;
}
__int64 cal() // 計算結果 (prime[i...]^p[i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++)
{
if( p[i] )
{
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //計算 (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
while(t--)
{
cin>>n>>m;
len = 0;
memset(p, 0, sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加進 P 中去才能使 (m+n)! / ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n, 1);
get(m, 0);
get(n+1, 0);
ans = cal();
printf("%I64d\n", ans);
}
return 0;
}
可以用素數分解法，
先求出上面和下面的素數表示，然後約分後，再用求冪公式
『叄』 acmdfs判斷無向圖是否有環
如果存在迴路，則必存在一個子圖，是一個環路。環路中所有頂點的度>=2。
n演算法：
第一步：刪除所有度<=1的頂點及相關的邊，並將另外與這些邊相關的其它頂點的度減一。
第二步：將度數變為1的頂點排入隊列，並從該隊列中取出一個頂點重復步驟一。
如果最後還有未刪除頂點，則存在環，否則沒有環。
n演算法分析：
由於有m條邊，n個頂點。
i)如果m>=n，則根據圖論知識可直接判斷存在環路。（證明：如果沒有環路，則該圖必然是k棵樹 k>=1。根據樹的性質，邊的數目m = n-k。k>=1，所以：m<n）
ii)如果m<n 則按照上面的演算法每刪除一個度為0的頂點操作一次（最多n次），或每刪除一個度為1的頂點（同時刪一條邊）操作一次（最多m次）。這兩種操作的總數不會超過m+n。由於m<n，所以演算法復雜度為O(n)。
註：
該方法，演算法復雜度不止O(V)，首先初始時刻統計所有頂點的度的時候，復雜度為(V + E)，即使在後來的循環中E>=V，這樣演算法的復雜度也只能為O(V + E)。其次，在每次循環時，刪除度為1的頂點，那麼就必須將與這個頂點相連的點的度減一，並且執行delete node from list[list[node]]，這里查找的復雜度為list[list[node]]的長度，只有這樣才能保證當degree[i]=1時，list[i]裡面只有一個點。這樣最差的復雜度就為O(EV)了。