1、求组合数C（n，r）的函数
int myc(int n,int r) { int sum=1; for(int i=1;i<=r;i++) sum=sum*(n+1-i)/i; return sum; }
2、求排列数A（n，r）的函数
int mya(int n,int r) { int sum=1; for(int i=0;i<r;i++) sum=sum*(n-i); return sum; }
1、一般的，在n个不同物体中，可重复选取r个物体的排列数是n^r。
2、从n个不同的物体中，允许重复的选取r个物体的组合数为C（n+r-1，r）。
3、一般的，在不全相异的物体中，其中n1个物体是相同的，n2个物体是相同的，...nk个物体是相同的。n个物体中不相同的物体是k个，即n=n1+n2+n3....+nk，则这几个物体全排列数是n!/（n1!×ｎ２！×．．．×ｎｋ！）。
定理：ｎ个有标号１，２，３，、、ｎ的顶点的树的数目是ｎ＾(n-2)．该定理说明用n-1条边将n个顶点连接的图有n^(n-2)个。
4、如果用Q（N,R）表示从N个不同元素中选取R个元素形成的圆周排列，那么Q（N,R）与A（N,R）的关系是Q（N,R）=A（N,R）/R.因为在取出的R个元素的圆周排列，每种排列重复了R次。Q（N,N）=（N-1）！。
推荐题目：poj 3252,1850,1019,1942,1496
poj 2084 递推，catalan数，注意是大整数，用java水过
import java.util.*; import java.math.BigDecimal; import java.math.*; import java.io.*; class Main { public static void main(String args[]) { Scanner cin=new Scanner(System.in); BigInteger f[]=new BigInteger[110]; f[0]=BigInteger.valueOf(1); f[1]=BigInteger.valueOf(1); f[2]=BigInteger.valueOf(2); for(int i=3;i<=100;i++) { f[i]=BigInteger.valueOf(0); for(int j=0;j<i;j++) { f[i]=f[i].add(f[j].multiply(f[i-j-1])); } } int n; while(cin.hasNext()) { n=cin.nextInt(); if(n==-1) break; System.out.println(f[n]); } } }
poj 1833 模拟和STL函数都可以，在此附上模拟代码，注意用c++交，否则TLE
#include<stdio.h> #include<stdlib.h> #define maxn 1024 int a[maxn+10]; int cmp(const void *e1,const void *e2) { return *((int *)e1)-*((int *)e2); } int main() { int t,n,k; int i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for( i=1;i<=n;i++) scanf("%d",&a[i]); a[0]=100000; for( i=0;i<k;i++) { for( j=n;j>=1&&a[j-1]>a[j];j--); if(j>=1) { int minlarge=a[j]; int minidx=j; for(int kk=j;kk<=n;kk++) if(minlarge>a[kk]&&a[kk]>a[j-1]) { minlarge=a[kk]; minidx=kk; } a[minidx]=a[j-1]; a[j-1]=minlarge; qsort(a+j,n-j+1,sizeof(int),cmp); } else { for( j=1;j<=n;j++) a[j]=j; } } for(j=1;j<=n;j++) printf("%d ",a[j]); printf(" "); } return 0; }
poj 1942 矩形格路径条数
#include<stdio.h> #include<algorithm> using namespace std; double myc(double n,double k) { double sum=1; for(double i=1;i<=k;i++) { sum=sum*(n-i+1)/i; } return sum; } int main() { //freopen("in.txt","r",stdin); double n,m; while(scanf("%lf%lf",&n,&m)!=EOF) { double ans=0; if(n==0&&m==0) break; if(n==0&&m>0) { printf("1 "); continue; } if(n>m) swap(n,m); ans=myc(n+m,n); printf("%.0lf ",ans); } return 0; }
poj 3252 组合计数
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; #define maxn 31 int c[maxn][maxn]; int power[maxn]; int binary[maxn]; int solve(int x) { if(x<=1) return 0; int n0,n1,len,res=0,i,j,k; for(i=0;i<maxn;i++) { if((power[i]&x)!=0) binary[i]=1; else binary[i]=0; } for(i=maxn-1;i>=0&&binary[i]==0;i--); for(len=i;len>=1;len--) { if(len%2==1) res+=(( power[len-1]-c[len-1][(len-1)/2])>>1); else res+=(power[len-1]>>1); } for(j=i,n0=0,n1=0;j>=0;j--) if(binary[j]) ++n1; else ++n0; if(n1<=n0) ++res; for(j=i-1,n0=0,n1=1;j>=0;j--) { if(binary[j]) { for(k=j;k>=0&&k+n0+1>=j-k+n1;k--) res+=c[j][k]; ++n1; } else ++n0; } return res; } int main() { //freopen("in.txt","r",stdin); int i,j; for( i=0;i<maxn;i++) { power[i]=(1<<i); c[i][0]=1; c[i][i]=1; } for(i=2;i<maxn;i++) for(j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; int start,finish; while(scanf("%d%d",&start,&finish)!=EOF) { printf("%d ",solve(finish)-solve(start-1)); } return 0; }
poj 1019 数学技巧
#include<stdio.h> #include<iostream> #include<cmath> #define maxn 32000 using namespace std; unsigned a[maxn],s[maxn]; void init() { a[1]=1; s[1]=1; for(int i=2;i<maxn;i++) { a[i]=a[i-1]+(int)log10((double)i)+1; s[i]=s[i-1]+a[i]; } } int solve(int n) { int i=1; while(s[i]<n) i++; int pos=0; pos=n-s[i-1]; //printf("%d ",pos); int len=0; for(i=1;len<pos;i++) len+=(int)log10((double)i)+1; //printf("%d ",len); return (i-1)/(int)pow(double(10),len-pos)%10; } int main() { int t; init(); scanf("%d",&t); while(t--) { int n; scanf("%d",&n); cout<<solve(n)<<endl; } return 0; }
poj 1496 组合计数
#include<stdio.h> #include<string.h> int main() { //freopen("in.txt","r",stdin); int C[30][30]; int i,j; for(i=0;i<=26;i++) { C[i][0]=1; C[i][i]=1; } for(i=2;i<=26;i++) for(j=1;j<i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1]; char str[20]; while(scanf("%s",str)!=EOF) { int len=strlen(str); for(i=0;i<len-1;i++) if(str[i]>=str[i+1]) break; if(i<len-1) { printf("0 "); continue; } __int64 sum=0; for(i=0;i<len;i++) sum+=C[26][i]; for(i=0;i<len;i++) { char ch; if(i==0) ch='a'; else ch=str[i-1]+1; for(char j=ch;j<str[i];j++) sum+=C['z'-j][len-i-1]; } printf("%I64d ",sum); } return 0; }