P1066 2^k進(jìn)制數(shù)

題目鏈接

題目描述

設(shè) r 是個(gè) 2^k進(jìn)制數(shù)何址，并滿足以下條件：

• r 至少是個(gè) 2 位的 2^k進(jìn)制數(shù)。
• 作為 2^k進(jìn)制數(shù)，除最后一位外，r的每一位嚴(yán)格小于它右邊相鄰的那一位庇茫。
• 將 r轉(zhuǎn)換為二進(jìn)制數(shù) q后嫉父，則 q的總位數(shù)不超過 w。

在這里缕题，正整數(shù) k,w 是事先給定的。

問：滿足上述條件的不同的 r共有多少個(gè)依痊？

我們?cè)購牧硪唤嵌茸餍┙忉專涸O(shè) S是長度為 w 的 0101 字符串（即字符串 S 由 w 個(gè) 0 或 1 組成）避除，S對(duì)應(yīng)于上述條件三中的 q怎披。將 S從右起劃分為若干個(gè)長度為 k的段，每段對(duì)應(yīng)一位 2^k 進(jìn)制的數(shù)瓶摆，如果 S至少可分成 2段凉逛，則 S所對(duì)應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的 2^k進(jìn)制數(shù) r。

例：設(shè) k=3,w=7 k =3群井。則 r 是個(gè)八進(jìn)制數(shù)（ 2^3=8 ）状飞。由于 w=7，長度為 7 的 01 字符串按 33位一段分书斜，可分為 3 段（即 1,3,3诬辈，左邊第一段只有一個(gè)二進(jìn)制位），則滿足條件的八進(jìn)制數(shù)有：

2 位數(shù)：
高位為 1：6 個(gè)（即 12,13,14,15,16,17 ）,
高位為 2：5 個(gè)荐吉，
…焙糟，
高位為 6：1個(gè)（即 67 ）。
共 6+5+…+1=21 個(gè)样屠。

3位數(shù)：
高位只能是 1穿撮，
第 2位為 2：5 個(gè)（即 123,124,125,126,127），
第 2 位為 3：4 個(gè)痪欲，
…悦穿，
第 2位為 6：1個(gè)（即 167）。
共 5+4+…+1=15 個(gè)业踢。

所以栗柒，滿足要求的 r共有 36 個(gè)。

輸入格式

一行兩個(gè)正整數(shù) k,w 用一個(gè)空格隔開：

輸出格式

一行一個(gè)個(gè)正整數(shù)知举，為所求的計(jì)算結(jié)果瞬沦。
即滿足條件的不同的 r的個(gè)數(shù)（用十進(jìn)制數(shù)表示），要求不得有前導(dǎo)零负蠕，各數(shù)字之間不得插入數(shù)字以外的其他字符（例如空格蛙埂、換行符、逗號(hào)等）遮糖。

（提示：作為結(jié)果的正整數(shù)可能很大，但不會(huì)超過 200 位）

解析

首先我們來理解題意叠赐，r為k進(jìn)制數(shù)欲账，轉(zhuǎn)化為二進(jìn)制后，01串最多位不能超過w芭概。由于k位01串可以組成一個(gè)k進(jìn)制數(shù)赛不，我們不妨將最多位可能的情況下的w按k位一組進(jìn)行切分霍弹，得到L = ceil(w/k)組纹笼，那么r在k進(jìn)制情況下最多有L位，最少有2位七冲。

例如輸入3，7時(shí)殿较，r位8進(jìn)制數(shù)耸峭，r的每位由3個(gè)二進(jìn)制位構(gòu)成，r最多情況下可能由7個(gè)二進(jìn)制位構(gòu)成淋纲。我們將7按3位一組進(jìn)行切分劳闹，得到[1,3,3]。

r在k進(jìn)制下最少只有兩位洽瞬，最多L位本涕，則r的所有情況為 2位r下的情況到L位r下的情況總數(shù)之和。

以 3 7為例伙窃，則r可能有2位或3位菩颖，當(dāng)r兩位的時(shí)候，可能情況有 12为障，13位他，14，..17,23,24..27,67产场，即在1..7的數(shù)字中選擇2個(gè)鹅髓，構(gòu)成二位的r。當(dāng)r三位時(shí)京景，即首先選擇出第一位窿冯，并在剩下的位中選擇出2個(gè)比第一位大的數(shù)。

由此确徙，可以看出這個(gè)問題實(shí)際上是組合數(shù)問題醒串。

當(dāng)前n個(gè)分段，每個(gè)分段均為k位時(shí)鄙皇，則每段可選擇的數(shù)字為2^{k-1芜赌，而r的可能情況為(2}k-1)中取i位(i從2到n)

最后一個(gè)分段有可能不到k位，則首先從1開始選擇伴逸，做出第一次選擇后缠沈，計(jì)算出剩下n-1個(gè)分段的組合數(shù)，并依次求和错蝴，得到最終結(jié)果洲愤。

接下來問題就轉(zhuǎn)換到如何計(jì)算組合數(shù)了。

計(jì)算組合數(shù)可以參考這篇博文 參考鏈接

此處使用楊輝三角遞推求解組合數(shù)值顷锰。

最后本題中會(huì)出現(xiàn)大整數(shù)柬赐，超出 long long int范圍，因此對(duì)于C++/C實(shí)現(xiàn)來說需要手寫大整數(shù)

在此首先給出Java版本代碼

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    private static final int n = 1000;
    static BigInteger [][]comb = new BigInteger[1000][1000];
    static void init()
    {
        for(int i=0;i<n ;i++)
        {
            comb[i][0] = BigInteger.valueOf(1);
            comb[i][i] = BigInteger.valueOf(1);
            for(int j=1;j<i;j++)
            {
                comb[i][j] = comb[i-1][j].add(comb[i-1][j-1]);
            }
        }

    }


    static BigInteger C(int n, int m)
    {
        if(n<m) return BigInteger.valueOf(0);
        return comb[n][m];
    }

    public static void main(String[] args) {
        BigInteger cnt =BigInteger.valueOf(0);
        init();
        int k,w;
        Scanner in = new Scanner(System.in);
        k = in.nextInt();
        w = in.nextInt();
        int fullPart = w / k;
        int divPart = (int) Math.ceil(1.0*w / k);
        int resPart = 0;
        if (w % k != 0)
        {
            resPart = (int) (w - k * fullPart);
        }
        int sel = (int) (Math.pow(2, k) - 1);
        for (int i = 2; i <= divPart; i++)
        {
            if (i != divPart)
            {
                cnt = cnt.add(C(sel,i));
            }
            else
            {
                if (resPart != 0)
                {
                    int t = (int) (Math.pow(2, resPart) - 1);
                    for (int j = 1; j <= t; j++)
                    {
                        cnt = cnt.add(C(sel-j,i-1));
                    }
                }
                else
                {
                    cnt = cnt.add(C(sel,i));
                }
            }

        }
        System.out.println(cnt);
    }
}

C語言代碼 此處大整數(shù)代碼來自于其他博文官紫，一時(shí)找不到出處

#include<stdio.h>
#include<string.h>
#include<math.h>
#define ll long long int
#define maxChar 130
#define maxlen 260
typedef struct HP
{int len;
char s[maxChar];
}HP;
void PrintHP(HP x) {for(int i=x.len;i>=1;i--) printf("%d",x.s[i]);}
void Str2HP(const char *s,HP *x)
{
    x->len=strlen(s);
    for(int i=1;i<=x->len;i++) x->s[i]=s[x->len-i]-'0'; //倒著記錄
}
void Plus(const HP a,const HP b,HP*c)
{
    int i;c->s[1]=0;
    for(i=1;i<=a.len||i<=b.len||c->s[i];i++){
        if(i<=a.len) c->s[i]+=a.s[i];
        if(i<=b.len) c->s[i]+=b.s[i];
        c->s[i+1]=c->s[i]/10;c->s[i]%=10;
    }
    c->len=i-1;if(c->len==0) c->len=1;
}
HP comb[maxlen][maxlen];
void init()
{
        for(int i=0;i<maxlen ;i++)
        {
            
            Str2HP("1",&comb[i][0]);
            Str2HP("1",&comb[i][i]);
            for(int j=1;j<i;j++)
            {
                Plus(comb[i-1][j],comb[i-1][j-1],&comb[i][j]);
            }
        }
}
HP C(ll n, ll m)
{
    HP t;
    Str2HP("0",&t);
    if(n<m) return t;
    return comb[n][m];
}

int main()
{
    HP ans;
    HP temp;
    ll cnt = 0;
    Str2HP("0",&ans);
    ll k, w;
    init();
    scanf("%lld %lld", &k, &w);
    ll fullPart = w / k;
    ll divPart = ceil(1.0*w / k);
    int resPart = 0;
    if (w % k != 0)
        resPart = w - k * fullPart;
    int sel = pow(2, k) - 1;
    for (int i = 2; i <= divPart; i++)
    {
        if (i != divPart)
        {
            HP t=  C(sel,i);
            HP a = ans;
            Plus(a,t,&ans);
        }
        else
        {
            if (resPart != 0)
            {
                int t = pow(2, resPart) - 1;
                for (int j = 1; j <= t; j++)
                {
                    HP x = C(sel - j, (i - 1));
                    HP a = ans;
                    Plus(a,x,&ans);
                }
            }
            else
            {
                HP x = C(sel, i);
                HP a = ans;
                Plus(a,x,&ans);
            }

        }

    }
    PrintHP(ans);
}