洛谷蓝题（点击跳转）
提高组 第四题
题目描述
设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^nint 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 ) );elsec[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 ) ) );elseinstead( c[i] , div( mul( c[i - 1] , i ) , i - most + 1 ) );ans = dif( ans , c[i] );}cout << ans;
}
