洛谷蓝题（点击跳转）
提高组 第四题
题目描述
设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< span>≤30000）是事先给定的。
问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），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：
3 7
输出样例#1：
36
代码有注解，直接看代码吧：
#include<bits/stdc++.h>
using namespace std;//比较主要是方便求和
inline bool comp(string a ,string b)
{
if( a.size() < b.size() )
return 0;
if( a.size() > b.size() )
return 1;
for( int i = a.size() - 1 ; i >= 0 ; i-- )
{
if( a[i] < b[i] )
return 0;
if( a[i] > b[i] )
return 1;
}
return 1;
}
//求两个数的和
inline string sum( string a , string b )
{
if( comp( a , b ) == 0 )
swap( a , b );
string c = "";
char x[2] = "";
bool n = 0;
int bpt = b.size() - 1;
for( int i = a.size() - 1 ; i >= 0 ; i-- )
{
if( b[bpt] < '0' || b[bpt] > '9' )
b[bpt] = '0';
x[0] = a[i] + b[bpt] - '0';
if( n == 1 )
{
x[0]++;
n = 0;
}
if( x[0] > '9' )
{
x[0] -= 10;
n = 1;
}
c.insert( 0 , x );
bpt--;
if( bpt < 0 )
{
bpt = 0;
b[0] = '0';
}
}
if( n == 1 )
c.insert( 0 , "1" );
while( c[0] == '0' )
c.erase( 0 , 1 );
if( c.size() == 0 )
c.insert( 0 , "0" );
return c;
}
//求两个数的差（保证结果为正数）
string dif( string a , string b )
{
string c = "";
char x[2] = "";
bool n = 0;
int bpt = b.size() - 1;
for( int i = a.size() - 1 ; i >= 0 ; i-- )
{
if( b[bpt] < '0' || b[bpt] > '9' )
b[bpt] = '0';
x[0] = a[i] - b[bpt] + '0';
if( n == 1 )
{
x[0]--;
n = 0;
}
if( x[0] < '0' )
{
x[0] += 10;
n = 1;
}
c.insert( 0 , x );
bpt--;
if( bpt < 0 )
{
bpt = 0;
b[0] = '0';
}
}
while( c[0] == '0' )
c.erase( 0 , 1 );
if( c.size() == 0 )
c.insert( 0 , "0" );
return c;
}
//求高精度数与整型数的积
string mul( string a , int b )
{
string c = "";
char x[2] = "";
int n = 0 , y;
for( int i = a.size() - 1 ; i >= 0 ; i-- )
{
y = 0;
if( n > 0 )
y = n;
n = ( a[i] - '0' ) * b + y;
x[0] = n % 10 + '0';
n /= 10;
if( x[0] > '9' )
{
x[0] -= 10;
n++;
}
c.insert( 0 , x );
}
while( n > 0 )
{
x[0] = n % 10 + '0';
n /= 10;
c.insert( 0 , x );
}
while( c[0] == '0' )
c.erase( 0 , 1 );
if( c.size() == 0 )
c.insert( 0 , "0" );
return c;
}
//求高精度数与整型数的商
string div( string a , int b )
{
string c = "";
char x[2] = "";
int n = 0 , y;
for( int i = 0 ; i < a.size() ; i++ )
{
n *= 10;
n += a[i] - '0';
x[0] = n / b + '0';
n %= b;
c.insert( c.size() , x );
}
while( n > 0 )
{
x[0] = n % 10 + '0';
n /= 10;
c.insert( 0 , x );
}
while( c[0] == '0' )
c.erase( 0 , 1 );
if( c.size() == 0 )
c.insert( 0 , "0" );
return c;
}
//把整型数转化成高精度数
string change( int num )
{
if( num == 0 )
return "0";
string a = "";
char c[2] = "";
while( num > 0 )
{
c[0] = num % 10 + '0';
num /= 10;
a.insert( 0 , c );
}
return a;
}
//覆盖（即用一个高精度数覆盖另一个高精度数）
void instead( string &s , string s0 )
{
s.erase( 0 , s.size() );
s.insert( 0 , s0 );
}
string c[50000];
const int power[10] = { 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 };//打表计算2^n
int main()
{
int k , w;
cin >> k >> w;
c[2] = change( ( power[k] - 1 ) * ( power[k] - 2 ) / 2 );
string ans = c[2];
int most = min( w / k + ( w % k == 0 ? 0 : 1 ) , power[k] - 1 );
//most存储max（max不能定义）
for( int i = 3 ; i <= most ; i++ )
{
if( ( power[k] - i ) % i == 0 )
c[i].insert( 0 , mul( c[i - 1] , ( power[k] - i ) / i ) );
else
c[i].insert( 0 , div( mul( c[i - 1] , power[k] - i ) , i ) );
ans = sum( ans , c[i] );
}
instead( c[most - 1] , "1" );
int most2 = min( power[w % k] - 1 , power[k] - most - 1 );
if( power[k] - most <= power[w % k] - 1 || most2 <= 0 )
{
cout << ans;
return 0;
}
//特殊情况，如3 17，最大234567，上限6位3起，这时会误判
ans = dif( ans , "1" );//首位为max-1时要减掉
for( int i = most ; i < power[k] - 1 - most2 ; i++ )
{
if( i % ( i - most + 1 ) == 0 )
instead( c[i] , mul( c[i - 1] , i / ( i - most + 1 ) ) );
else
instead( c[i] , div( mul( c[i - 1] , i ) , i - most + 1 ) );
ans = dif( ans , c[i] );
}
cout << ans;
}