洛谷藍題（點擊跳轉(zhuǎn)）

提高組 第四題

題目描述

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

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

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

（3）將r轉(zhuǎn)換為2進制數(shù)q后，則q的總位數(shù)不超過w。

在這里，正整數(shù)k（1≤k≤9）和w（k<W< span>≤30000）是事先給定的。

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

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

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

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

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

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

輸入輸出格式

輸入格式：

輸入只有1行，為兩個正整數(shù)，用一個空格隔開：

k W

?

輸出格式：

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

（提示：作為結(jié)果的正整數(shù)可能很大，但不會超過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;
}
//求兩個數(shù)的和
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;
}
//求兩個數(shù)的差（保證結(jié)果為正數(shù)）
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;
}
//求高精度數(shù)與整型數(shù)的積
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;
}
//求高精度數(shù)與整型數(shù)的商
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;
}
//把整型數(shù)轉(zhuǎn)化成高精度數(shù)
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;
}
//覆蓋（即用一個高精度數(shù)覆蓋另一個高精度數(shù)）
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;
}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/weilinxiao/p/11169741.html

總結(jié)

以上是生活随笔為你收集整理的P1066 2^k进制数 NOIP 2006 提高组 第四题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。