首页 > 代码库 > 【noi 2.6_9288】&【hdu 1133】Buy the Ticket（DP / 排列组合 Catalan+高精度）
【noi 2.6_9288】&【hdu 1133】Buy the Ticket（DP / 排列组合 Catalan+高精度）
题意：有m个人有一张50元的纸币，n个人有一张100元的纸币。他们要在一个原始存金为0元的售票处买一张50元的票，问一共有几种方案数。
解法：（学习了他人的推导后~）
1.Catalan数的应用7的变形。（推荐阅读：http://www.cnblogs.com/chenhuan001/p/5157133.html）。P.S.不知我之前自己推出的公式“C(n,m)*C(2*m,m)/(m+1)*P(n,n)*P(m,m)”是否是正确的。
（1）在不考虑m人和n人本身组内的排列时，总方案数为C(m+n,n)或C(m+n,m)。
（2）而不合法的设1为50元（m个），0为100元（n个）。那么便有10110...设前2k+1个数中有k+1个0和k个1，因此不合法。而将2k+1之后的所有0（n-k-1个）和1（m-k个）异或。这样的转换是唯一对应的，不合法的方案数仍不会改变，因此可行，得到n-k-1个1和m-k个0。总共n-1个1和m+1个0。这样不合法的方案数就可用C(n+m,n-1)或C(n+m,m+1)表示了。
由于（1）-（2）已经包含了m人和n人跨组之间的组合，于是只乘上m人和n人本身组内的排列P(m,m)和P(n,n)表示答案，而不是P(n+m,n+m)。化简可得(m+n)! (m-n+1)/(m+1)。
2.隔板法。(不知道这个方法是不是这么叫......)
（1）先放了n个5元，构成n+1个空位。再一个个放m个100元，第一个，除了第1个空不可，其它位置都可放，合法的概率为n/(n+1)。第二个100元，概率变为(n-1)/n。以此类推，第m个的概率就是(n-m+1)/(n-m+2)。那么这m个100元的合法的总概率就是所有的概率相乘，得到(n-m+1)/(n+1)。
（2）然后再考虑这n+m个的排列方法P(n+m,n+m)，与原来的相乘。
最终得到(n+m)!*(n-m+1)/(n+1).
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define N 110 7 8 struct node 9 {10 int s[510];11 int l;12 node() {l=0;memset(s,0,sizeof(s));}13 };14 node multi(node x,int y)//dif from +15 {16 node z;17 z.l=x.l;18 for (int i=1;i<=x.l;i++)19 {20 z.s[i]+=x.s[i]*y;21 if (z.s[i]>9) z.s[i+1]+=z.s[i]/10,z.s[i]%=10;22 }23 while (z.s[z.l+1])24 {25 z.l++;26 if (z.s[z.l]>9) z.s[z.l+1]+=z.s[z.l]/10,z.s[z.l]%=10;27 }28 return z;29 }30 node conv(node x)31 {32 node z;33 z.l=x.l;34 for (int i=1;i<=x.l;i++)35 z.s[x.l-i+1]=x.s[i];36 return z;37 }38 node div(node x,int y)39 {40 node z;41 int t=x.l+1,h=0;42 while (h<y && t>1) h=10*h+x.s[--t];43 z.s[++z.l]=h/y,h%=y;44 while (t>1)45 {46 h=10*h+x.s[--t];47 z.s[++z.l]=h/y,h%=y;48 }49 z=conv(z);50 return z;51 }52 /*另一种打法53 node div(node x,int y)//crucial54 {55 node z;56 int t=x.l+1,h=0;57 while (t>1)//converse!58 {59 bool tf=true;60 while (h<y && t>1)61 {62 h=10*h+x.s[--t];63 if (!tf&&z.l) z.s[++z.l]=0;//商最高位之后才开始赋值0，并且要是加入新的一位为064 tf=false;65 }66 z.s[++z.l]=h/y,h%=y;67 }68 z=conv(z);69 return z;70 }71 */72 void print(node x)73 {74 for (int i=x.l;i>=1;i--)75 printf("%d",x.s[i]);76 printf("\n");77 }78 node P(int x)79 {80 node z;81 z.l=z.s[1]=1;82 for (int i=x;i>=1;i--)83 z=multi(z,i);84 return z;85 }86 int main()87 {88 int n,m;89 while (1)90 {91 scanf("%d%d",&n,&m);92 if (!n&&!m) break;93 if (n<m) {printf("0\n");continue;}94 print(div(multi(P(n+m),n-m+1),n+1));95 }96 return 0;97 }
3.动态规划。转载自：http://blog.csdn.net/clover_hxy/article/details/52931233
f[i][j]表示到第i个人，已经有j个人用50元买了门票。
f[i][j]=f[i-1][j]+f[i-1][j-1]; （f[i-1][j]表示当前这个人用100元，f[i-1][j-1]表示当前这个人用50元。设k=i-j 即100元的个数，递推的时候保证k<=j。）
因为每个人是不一样的所以最后的答案是 f[n+m][n]*n!*m!。
P.S.看！DP一个状态递推就能省了上面2种一长串的头脑风暴推导过程，可见DP的优越性。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define N 103 7 using namespace std; 8 struct data{ 9 int num[403]; 10 }f[N*2][N],ans; 11 int n,m,a[N],b[N],c[N]; 12 int calc(int a[N],int x) 13 { 14 a[0]=1; a[1]=1; 15 for (int i=1;i<=x;i++) 16 { 17 for (int j=1;j<=a[0];j++) 18 a[j]*=i; 19 for (int j=1;j<=a[0];j++) { 20 a[j+1]+=a[j]/10000; 21 a[j]%=10000; 22 } 23 int t=a[0]; 24 while (a[t+1]) { 25 t++; 26 a[t+1]+=a[t]/10000; 27 a[t]%=10000; 28 } 29 a[0]=t; 30 } 31 } 32 void add(data &x,data y,data z) 33 { 34 int t=max(y.num[0],z.num[0]); 35 for (int i=1;i<=t;i++) 36 x.num[i]=y.num[i]+z.num[i]; 37 for (int i=1;i<=t;i++) 38 x.num[i+1]+=x.num[i]/10000,x.num[i]%=10000; 39 while (x.num[t+1]){ 40 t++; 41 x.num[t+1]+=x.num[t]/10000; 42 x.num[t]%=10000; 43 } 44 x.num[0]=t; 45 } 46 void mul(data &x,int a[N]) 47 { 48 memset(c,0,sizeof(c)); 49 for (int i=1;i<=x.num[0];i++) 50 for (int j=1;j<=a[0];j++) 51 c[i+j-1]+=x.num[i]*a[j]; 52 int t=max(x.num[0],a[0]); 53 for (int i=1;i<=t;i++) 54 c[i+1]+=c[i]/10000,c[i]%=10000; 55 while(c[t+1]) { 56 t++; 57 c[t+1]+=c[t]/10000; 58 c[t]%=10000; 59 } 60 c[0]=t; 61 for (int i=0;i<=c[0];i++) x.num[i]=c[i]; 62 } 63 int main() 64 { 65 freopen("a.in","r",stdin); 66 freopen("my.out","w",stdout); 67 int n=100; int m=100; 68 f[0][0].num[0]=1; 69 f[0][0].num[1]=1; 70 for (int i=1;i<=n+m;i++) 71 for (int j=min(i,n);j>=1;j--) 72 { 73 int k=(i-j); 74 if (k>j) break; 75 add(f[i][j],f[i-1][j],f[i-1][j-1]); 76 } 77 int cnt=0; 78 while (true){ 79 scanf("%d%d",&n,&m); cnt++; 80 if (n==0&&m==0) break; 81 memset(a,0,sizeof(a)); 82 memset(b,0,sizeof(b)); 83 calc(a,n); calc(b,m); 84 for (int i=0;i<=400;i++) ans.num[i]=0; 85 for (int i=0;i<=f[n+m][n].num[0];i++) 86 ans.num[i]=f[n+m][n].num[i]; 87 mul(ans,a); mul(ans,b); 88 printf("Test #%d:\n",cnt); 89 if (ans.num[0]==0||n<m) { 90 printf("0\n"); 91 continue; 92 } 93 for (int i=ans.num[0];i>=1;i--){ 94 int t=ans.num[i]; 95 if (i!=ans.num[0]){ 96 if (t<10) printf("000"); 97 else if (t<100) printf("00"); 98 else if (t<1000) printf("0"); 99 }100 printf("%d",t);101 }102 printf("\n");103 } 104 }
【noi 2.6_9288】&【hdu 1133】Buy the Ticket（DP / 排列组合 Catalan+高精度）