【题解】洛谷P1066 [NOIP2006TG] 2^k进制数(复杂高精+组合推导)

洛谷P1066：https://www.luogu.org/problemnew/show/P1066

思路

挺难的一道题 也很复杂

满足题目要求的种数是两类组合数之和

r的最多位数m为

w/k（当w mod k=0 时）w/k+1（当 w mod k=1 时）

First:

位数为2~m的种数

即从2^k-1中不重复地取i个的组合数(只取到2^k-1是因为2^k会进位)

即C(2^k-1,2)+C(2^k-1,3)+...+C(2^k-1,m)

Second:

位数为m+1的种数

因为要每个数严格小于左边

所以枚举第一位的值i 再取其他的组合数C(2^k-1-i,m)

代码

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int total[310];//存高精ans int k,w,n,m,c; int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); } void C(int n,int m) { if(n<m) return; int a[310],b[310],x,g; for(int i=m;i>=1;i--) { a[i]=n+i-m;//分子的因子n!/(n-m)! b[i]=i;//分母的因子m! } for(int i=1;i<=m;i++)//约分 去掉分母b[i] { if(b[i]==1) continue; for(int j=m;j>=1;j--)//高精除法 { x=gcd(b[i],a[j]); b[i]/=x; a[j]/=x; if(b[i]==1) break; } } memset(b,0,sizeof(b)); b[1]=1,b[0]=1; for(int j=1;j<=m;j++)//约分后的分子相乘 { g=0; if(a[j]==1) continue; for(int i=1;i<=b[0];i++) { b[i]=b[i]*a[j]+g;//高精乘法 g=b[i]/10; b[i]%=10; if(i==b[0]&&g!=0) b[0]++;//如果还要进位 说明长度要加1 } } total[0]=max(total[0],b[0]); for(int i=1;i<=total[0];i++)//高精加法 { total[i]+=b[i]; total[i+1]+=total[i]/10; total[i]%=10; } if(total[total[0]+1]!=0) total[0]++;//如果还要进位 说明长度要加1 } int main() { cin>>k>>w; n=(1<<k)-1;//2^k-1 c=w%k; m=w/k;//最高位数 for(int i=m;i>=2;i--) C(n,i);//计算位数为2~len-1的组合数 c=(1<<c)-1;//最高位可取最大值 if(c>=1&&n>m)//计算位数为len的组合数 for(int i=1;i<=c;i++) C(n-i,m);//第一位取了i 后面只能取n-i 且要取m个 for(int j=total[0];j>=1;j--) cout<<total[j];//逆序输出ans } View Code

 

转载于:https://www.cnblogs.com/BrokenString/p/9677967.html