【题解】洛谷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[];//存高精ans

int k,w,n,m,c;

int gcd(int a,int b)

{

    if(a%b==) return b;

    else return gcd(b,a%b);

}

void C(int n,int m)

{

    if(n<m) return;

    int a[],b[],x,g;

    for(int i=m;i>=;i--)

    {

        a[i]=n+i-m;//分子的因子n!/(n-m)!

        b[i]=i;//分母的因子m!

    }

    for(int i=;i<=m;i++)//约分 去掉分母b[i]

    {

        if(b[i]==) continue;

        for(int j=m;j>=;j--)//高精除法

        {

            x=gcd(b[i],a[j]);

            b[i]/=x;

            a[j]/=x;

            if(b[i]==) break;

        }

    }

    memset(b,,sizeof(b));

    b[]=,b[]=;

    for(int j=;j<=m;j++)//约分后的分子相乘

    {

        g=;

        if(a[j]==) continue;

        for(int i=;i<=b[];i++)

        {

            b[i]=b[i]*a[j]+g;//高精乘法

            g=b[i]/;

            b[i]%=;

            if(i==b[]&&g!=) b[]++;//如果还要进位 说明长度要加1

        }

    }

    total[]=max(total[],b[]);

    for(int i=;i<=total[];i++)//高精加法

    {

        total[i]+=b[i];

        total[i+]+=total[i]/;

        total[i]%=;

    }

    if(total[total[]+]!=) total[]++;//如果还要进位 说明长度要加1

}

int main()

{

    cin>>k>>w;

    n=(<<k)-;//2^k-1

    c=w%k;

    m=w/k;//最高位数

    for(int i=m;i>=;i--) C(n,i);//计算位数为2~len-1的组合数

    c=(<<c)-;//最高位可取最大值

    if(c>=&&n>m)//计算位数为len的组合数

        for(int i=;i<=c;i++) C(n-i,m);//第一位取了i 后面只能取n-i 且要取m个

    for(int j=total[];j>=;j--) cout<<total[j];//逆序输出ans

}

巴特西

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

First:

Second:

代码

最新文章

热门文章