题解 P1066 【2^k进制数】

p878567 · 2017-11-20 22:12:09 · 题解

基于排列组合的新算法，史上最快（用时0ms）。

先补充一个知识点：对一个n位的2^k进制数，其转化成二进制数后的位数为nk（也有可能较少，因为有前导0的存在，前导0的个数取决于原数的第一位）。

由此，我们知道，这个要求的数的位数不超过w/k向上取整。

而另一方面，又有最多只有2^k-1个数，因此最多2^k-1位。

两个数中取较小的一个就是位置上限。

根据题意，从所有n个数中选m个数后，只有一种组合方式，即m位数的数量是C^m_n=\frac{n*(n-1)*...*(n-m+1)}{m*(m-1)*...*1}

总数量是\sum_{i=2}^{min(w/k+(w\%k==0?0:1),power[k]-1)}{C^i_n}

这里n=2^k-1

为了方便计算，可以推出C^m_n=C^{m-1}_n*\frac{n-m+1}{m}

根据这个递归式，可以快速算出结果

但由于前导0的存在，部分场合下会算大，如样例中234也会被包含进去，解决方法就是把它减掉。

由于原位数相同，二进制位数仅取决于前导0的个数，这又取决于原数的首位。

原数的首位同时受位数和对应前导0个数的限制，位数：2^k-max-1，首位2^(w%k)-1。

位数中，max为最大位数，首位的表达式的证明涉及进制转换等一系列方面的内容，这里不做证明，有兴趣可自己证。

受数据取法影响，当位数为max，首位为m时，就相当于在2^k-1-m个数中取max-1个，显然可以用C来表示。

仿照前面，我们得到最后答案ans=\sum_{i=2}^{min(w/k+(w\%k==0?0:1),power[k]-1)}{C^i_n}-\sum_{i=2}^{min(power[w\%k]-1,power[k]-most-1)}{C^{max-1}_i}

与递归式C^m_n=C^m_{n-1}*\frac{n}{n-m},C^n_n=1

计算时要反过来，即首位m先取2^k-max，再逐渐降到上限。

代码不重要，会写高精度总是写得出来的，不会的也看不懂，不过发上：

#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;
}