noip2006 2^k进制数解题报告

  2^k进制数解题报告

    

【问题描述】

设r是个2k 进制数，并满足以下条件：

（1）r至少是个2位的2k 进制数。

（2）作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。

（3）将r转换为2进制数q后，则q的总位数不超过w。

在这里，正整数k（1≤k≤9）和w（k<w≤30000）是事先给定的。

问：满足上述条件的不同的r共有多少个？

【分析】

    k<=2^9=512,w<=30000，这题的数据大，显然不可能朴素搜索或枚举。但是如果我们加以分析，其实这道题还是很简单的。

    先看几个简单的问题。首位不为0的m位n进制数有几个？显然可以看出来，有（n-1）*n^(m-1）个。再加一个要求，要求每位的数字各不相同呢？这时候问题其实就可以转化成一个排列问题，即在n个数取m个不同的数的所有排列，有p（n，m）个，而在这题中，r的每一位严格小于它右边相邻的那一位，也就是说是有序的，且不重复的。无关顺序，也就是组合问题，不难看出有C（n，m）。

    可以说，这道题到这已经很明晰了。只需要枚举位数，求出每种位数的方案数，组合数可以预先用杨辉三角处理。但是这道题说的是转换为二进制数后总位数不超过w，而不是2^k进制数下不超过w。因为是2^k进制数，因此我们可以很容易求出他的最大位数，即w/k上取整，但是如果w不能被k整除，那么最高位的值就不能全部取到。因此当位数达到最大时，这里还要对最高位特殊处理，枚举最高位的值，然后再进行计算。

    这道题数据比较大，需要用到高精计算，最好压位一下。

【代码】

    

type arr=array[0..100]of longint;
var i,j,n,m,k,l,b:longint;
    c:array[0..520,0..520]of arr;
    ans:arr;
function plus(a,b:arr):arr;
var i,j,k,x:longint;
begin
  if a[0]>b[0] then k:=a[0] else k:=b[0];
  x:=0;
  for i:=1 to k do
  begin
   if a[0]>=i then x:=x+a[i];
   if b[0]>=i then x:=x+b[i];
   plus[i]:=x mod 10000;
   x:=x div 10000;
  end;
  plus[0]:=k;
  if x>0 then begin inc(plus[0]);plus[plus[0]]:=x;end;
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
begin
  assign(input,'digital.in');reset(input);
  assign(output,'digital.out');rewrite(output);
  readln(n,m);
  b:=1;
  for i:=1 to n do b:=2*b;
  c[0,0][0]:=1;c[0,0][1]:=1;
  for i:=1 to b do
  begin
   c[i,0][1]:=1;c[i,0,0]:=1;
   for j:=1 to i do
    c[i,j]:=plus(c[i-1,j],c[i-1,j-1]);
  end;
  ans[0]:=1;ans[1]:=0;
  for i:=2 to min(m div n,b-1) do
   ans:=plus(ans,c[b-1,i]);
  k:=1 shl (m mod n)-1;
  if m mod n<>0 then
   for i:=1 to min(b-m div n-1,k) do ans:=plus(ans,c[b-i-1,m div n]);
  write(ans[ans[0]]);
  for i:=ans[0]-1 downto 1 do
   if ans[i]<10 then write('000',ans[i])
   else if ans[i]<100 then write('00',ans[i])
   else if ans[i]<1000 then write('0',ans[i])
   else write(ans[i]);
  close(input);close(output);
end.