传送门
读懂题意过后，我们会发现，难点就是在于最高位的选取，因为最高位的组成有w%k位，并不是简单的k位。
不过我们可以分开做，我们先算小于等于\({{w} \over {k}}\)的选取方案，也就是说除去最高位的。相当于就是从1~\(2^k\)-1里选i个数，总方案数为
\(\sum_{i=2}^{w/k} C_{2^{k}-1}^{i}\)
如果考虑进最高位，首位的范围小于\(2^{w mod k}\)，由于要使右边的数都大于它，相当于就是从剩下的\(2^k-i\)个可选取的数中再选\({{w} \over {k}}\)个，即方案数为
\(\sum_{i=1}^{2^{w mod k}-1} C_{2^{k}-i-1}^{w/k}\)
其实上面的式子还不够完美，在写组合数公式时，往往要考虑到\(C_{a}^{b}\)中b绝对不能大于a，因此还要取个min特判一下，不然会WA一两个点
这道题还要用高精度，采用很方便的结构体高精度即可，我写的是压位版本的，比不压位的空间，时间复杂度都要快很多很多
#include<bits/stdc++.h> using namespace std; const int mod=100000000; struct bignum{ int num[30]; int len; bignum(int x) { len=1; num[1]=x; } bignum() { memset(num,0,sizeof(num)); len=0; } }a[525][525]; bignum operator +(const bignum &x,const bignum &y) { bignum z; z.len=max(x.len,y.len); for(int i=1;i<=z.len;i++) z.num[i]=x.num[i]+y.num[i]; for(int i=1;i<=z.len;i++) { z.num[i+1]+=z.num[i]/mod; z.num[i]%=mod; if(z.num[z.len+1]) z.len++; } return z; } void Print(bignum &A) { cout<<A.num[A.len]; for(int i=A.len-1;i>=1;i--) printf("d",A.num[i]);//不足八位自动补零 } bignum one(1); bignum ans; void YH_print() { for(int i=0;i<=520;i++) { a[i][0]=one,a[i][i]=one; } for(int i=2;i<=520;i++) { for(int j=1;j<=i;j++) { a[i][j]=a[i-1][j]+a[i-1][j-1]; } } }//杨辉三角 a[i][j]可以直接取出C(i,j)的值 int k,w,len,m,n1,n2; int main() { cin>>k>>w; len=w/k; m=w%k; n1=pow(2,k); n2=pow(2,m);//最高位取值 YH_print(); for(int i=2;i<=len&&i<n1;i++) ans=ans+a[n1-1][i]; for(int i=1;i<n2&&i<n1-len;i++) ans=ans+a[n1-i-1][len]; Print(ans); return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9581782.html
相关资源：各显卡算力对照表！