UVA - 1649 Binomial coefficients (组合数+二分)

题意：求使得C(n,k)=m的所有的n,k

根据杨辉三角可以看出，当k固定时，C(n,k)是相对于n递增的；当n固定且k<=n/2时，C(n,k)是相对于k递增的，因此可以枚举其中的一个，然后二分另一个。

我的方法是先预处理出2000以内的全部组合数，然后枚举n，二分找到对应的k<=n/2，然后把(n,k)和(n,n-k)加入到set中。

但这样做有一个缺陷，就是当k太小的时候，n可能会很大，数组存不下，因此当k比较小的时候，应该单独枚举k然后二分找到n。

k=1的时候不用算，直接加入即可。

注意溢出的问题。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef double db;

 const ll N=+,inf=0x3f3f3f3f3f3f3f3f;

 const ll up[]= {,,,,,};

 ll m,C[N][N];

 struct D {

     ll n,k;

     bool operator<(const D& b)const {return n!=b.n?n<b.n:k<b.k;}

 };

 set<D> ans;

 ll c(ll n,ll k) {

     ll ret=;

     for(ll i=; i<=k; ++i)ret=ret*(n-i+)/i;

     return ret;

 }

 ll bi(ll l,ll r,ll k) {

     while(l<=r) {

         ll mid=(l+r)>>;

         ll t=c(mid,k);

         if(t==m)return mid;

         t<m?l=mid+:r=mid-;

     }

     return -;

 }

 int main() {

     C[][]=;

     for(ll i=; i<N; ++i)

         for(ll j=; j<=i; ++j)

             C[i][j]=j==||j==i?:min(inf,C[i-][j]+C[i-][j-]);

     ll T;

     for(scanf("%lld",&T); T--;) {

         ans.clear();

         scanf("%lld",&m);

         for(ll i=; i<N; ++i) {

             ll j=lower_bound(C[i],C[i]+i/+,m)-C[i];

             if(C[i][j]==m)ans.insert({i,j}),ans.insert({i,i-j});

         }

         ans.insert({m,}),ans.insert({m,m-});

         for(ll i=; i<=; ++i) {

             ll j=bi(i,up[i],i);

             if(j!=-)ans.insert({j,i}),ans.insert({j,j-i});

         }

         printf("%lld\n",ans.size());

         ll f=;

         for(D x:ans) {

             f?f--:printf(" ");

             printf("(%lld,%lld)",x.n,x.k);

         }

         puts("");

     }

     return ;

 }

巴特西

UVA - 1649 Binomial coefficients (组合数+二分)

最新文章

热门文章