noip2006 2^k進制數 （組合數學）

P13152^k進制數

​​Accepted​​

标簽：

​​組合數學​​​

​​​數論​​​

​​​NOIP提高組2006​​

描述

設r是個2^k 進制數，并滿足以下條件：

（1）r至少是個2位的2^k 進制數。

（2）作為2^k 進制數，除最後一位外，r的每一位嚴格小于它右邊相鄰的那一位。

（3）将r轉換為2進制數q後，則q的總位數不超過w。

在這裡，正整數k（1≤k≤9）和w（k＜W≤30000）是事先給定的。

問：滿足上述條件的不同的r共有多少個？

我們再從另一角度作些解釋：設S是長度為w 的01字元串（即字元串S由w個“0”或“1”m組成），S對應于上述條件（3）中的q。将S從右起劃分為若幹個長度為k 的段，每段對應一位2^k進制的數，如果S至少可分成2段，則S所對應的二進制數又可以轉換為上述的2^k 進制數r。

例：設k=3，w=7。則r是個八進制數（23=8）。由于w=7，長度為7的01字元串按3位一段分，可分為3段（即1，3，3，左邊第一段隻有一個二進制位），則滿足條件的八進制數有：

2位數：高位為1：6個（即12，13，14，15，16，17），高位為2：5個，…，高位為6：1個（即67）。共6+5+…+1=21個。

3位數：高位隻能是1，第2位為2：5個（即123，124，125，126，127），第2位為3：4個，…，第2位為6：1個（即167）。共5+4+…+1=15個。

是以，滿足要求的r共有36個。

格式

輸入格式

輸入檔案隻有1行，為兩個正整數，用一個空格隔開：

k W

輸出格式

輸出檔案為1行，是一個正整數，為所求的計算結果，即滿足條件的不同的r的個數（用十進制數表示），要求最高位不得為0，各數字之間不得插入數字以外的其他字元（例如空格、換行符、逗号等）。

（提示：作為結果的正整數可能很大，但不會超過200位）

樣例1

樣例輸入1[複制]

3 7

樣例輸出1[複制]

36

限制

1s

來源

NOIP2006第四題

解析：摘自hzwer：

題目中的那個從另一角度分析就已經蘊含了這個題的基本思路。就以題目的例子為例，長度為7位的01字串按3位一段就這樣分：0 000 000。其中除了首段，每段都小于(111)2，也即小于2k，而首段自然是小于2w%k（對于w%k為0時也成立）了。

   如果首段為0，則當這個2k進制數位數分别為2、3、…、[n/k]時，如果用b_max表示2k，對應的解的個數分别為C[b_max-1][2]、C[b_max-1][3]、…、C[b_max-1][n/k]（C[i][j]表示從i個數裡選j個構成一組組合）。

   如果首段不為0，設首段為x，則解就有c[b_max-x-1][n/k]個。

#include<cstdio>
#include<algorithm>
#define maxn1 200
#define maxn2 1000
using namespace std;

int ans[maxn1+20];
int f[maxn2+100][maxn1+20];

void add(int a[],int b[])
{
  int i,j,k,last=0;
  a[0]=max(a[0],b[0]);
  for(i=1;i<=a[0];i++)
    {
      a[i]+=b[i]+last;
      last=a[i]/10,a[i]%=10;
    }
  if(last>0)a[++a[0]]=last;  
}

int main()
{
  int i,j,k,x,y,w;
  scanf("%d%d",&k,&w);
  if(w<=k){printf("0\n");return 0;}
  
  y=(1<<k)-1;
  if(w%k==0)x=y,k=w/k-1;
  else x=(1<<(w%k))-1,k=w/k;
   
  f[1][0]=1,f[1][1]=1;  
  ans[0]=0;
  
  for(i=1;i<=y;i++)
    {
      for(j=i+1;j>=1;j--)
      add(f[j],f[j-1]);
    if(i>=y-x && i<y)add(ans,f[k+1]);  
    }
  for(i=3;i<=k+1;i++)add(ans,f[i]);
  for(i=ans[0];i>=1;i--)printf("%d",ans[i]);
  printf("\n");  
  return 0;
}