题解

70 条题解

  • 2
    @ 2017-09-08 15:41:12

    这道题看到小伙伴们有用组合做的,那我就来一个DP吧。

    状态: F[i] 表示当前枚举下最大位为i的数个数 (F是一个滚动数组,E数组的存在无特殊意义,只是为了求后缀和)

    方程: F[i]=sum(F[j]) (i>j && i<2^K && i<2^W)(注意这个W是在不断变小的)

    解法:由原题可知,我们可以先把这个大数的前部分分为W/K个数位,由于进制是2^K,于是这里每个数位转化成十进制的取值都是【1,2^K-1】。但又由于W不一定被K整除,所以可能还会多出来一截数位,假设其长度为X(X<W),而这个数位转化的取值则是【1,2^X-1】。然后我们开始从第一位枚举每个数位,及时将答案保存并清空之前的统计,就可以统计不同长度下合法数的总个数,详细规则看一下题意就明白了,它已经说得很全面了。

    此代码已忽略高精度,很短。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    int K, W, N;
    int F[1200], E[1200];
    int main () {
        
        cin >> K >> W;
        N=((1<<K)-1);
        for(int i=1; i<=N; i++) F[i]=1;
        int x, ans=0;
        while(1) {
            W-=K;
            if (W<=0) break;
            if (W>K) x=N;
            else x=(1<<W)-1;
            for(int i=N; i>=1; i--) E[i]=E[i+1]+F[i], F[i]=0;
            for(int i=x; i>=1; i--) F[i]=E[i+1], ans=ans+F[i];
        }
        printf("%d", ans);
        
    }  
    

    完全版本。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    struct BIGINT {
        int len, num[105];  
        void CLEAR () {
            len=1;
            memset(num, 0, sizeof(num));    
        }
        void PRINT () {
            //printf("%d\n", len);
            for(int i=len; i>=1; i--) printf("%d", num[i]);     
        }
        BIGINT () {
            CLEAR();
        }
        BIGINT (int x) {
            CLEAR();    
            while(x) {
                num[len]=x%10;
                x/=10;
                len++;  
            }
            len--;
        }
        BIGINT operator + (BIGINT x) {
            BIGINT a;
            int maxlen=max(len, x.len);
            for(int i=1; i<=maxlen;i++) a.num[i]=num[i]+x.num[i];
            while(a.num[a.len]>=10||a.len<maxlen) {
                a.num[a.len+1]+=a.num[a.len]/10;
                a.num[a.len++]%=10;
            }    
            return a;
        }
        BIGINT operator * (BIGINT x) {
            BIGINT a;
            int maxlen=len+x.len-1;
            for(int i=1; i<=len; i++) 
                for(int j=1; j<=x.len; j++)
                    a.num[i+j-1]+=num[i]*x.num[j];
            while(a.num[a.len]>=10||a.len<maxlen) {
                a.num[a.len+1]+=a.num[a.len]/10;
                a.num[a.len++]%=10;
            }    
            return a;
        }
        bool operator == (BIGINT x) {
            if (len!=x.len) return 0;
            for(int i=1; i<=len; i++) 
                if (num[i]!=x.num[i]) return 0;
            return 1;    
        }
        bool operator > (BIGINT x) {
            if (len<x.len) return 0;
            else if (len>x.len) return 1;
            for(int i=len; i>=1; i--) 
                if (num[i]>x.num[i]) return 1;
                else  if (num[i]<x.num[i]) return 0;
            return 0;   
        }
    };
    int K, W, N;
    BIGINT F[1200], E[1200];
    int main () {
        
        cin >> K >> W;
        N=((1<<K)-1);
        for(int i=1; i<=N; i++) F[i]=1;
        int x;
        BIGINT ans=0;
        while(1) {
            W-=K;
            if (W<=0) break;
            if (W>K) x=N;
            else x=(1<<W)-1;
            for(int i=N; i>=1; i--) E[i]=E[i+1]+F[i], F[i]=0;
            for(int i=x; i>=1; i--) F[i]=E[i+1], ans=ans+F[i];
        }
        ans.PRINT();
        
    }  
    
  • 2
    @ 2015-10-16 23:27:24

    ###Pascal
    作为一只数竞狗,首选方法是搞一搞公式,然后写一个组合数表,高精度加一加就行了。
    前面似乎有人给了公式,这里解释一下公式怎么来的。
    1. 写成余数式:w=__p__*k+__r__ 这样在2^k进制下,最高位是0..(2^r)-1,后面的p位是0..(2^k)-1。←shl优先级大于+-,其实括号多余的,不过好看。
    2. 首位为0时,后面p位相当于从1..(2^k)-1取出p个数字,从1开始是因为右边严格大于左边。
    当然这里p换成p-1也可以,空两位;
    换成p-2,空三位;
    ...
    换成2,空p-2位,剩下2位,不能更少了╮(╯▽╰)╭
    以上:**Sigma[C[2^k-1,i],{i,2,p}]**
    3. 首位为1..(2^r)-1时,后面一定是p位,且依次取的是(首位+1)..(2^k)-1
    对首位的所有可能求和:**Sigma[C[2^k-1-i,p],{i,1,2^r-1}]**

    下面上代码,实际写的时候还有两个要注意的:
    1. dp求组合数表的初始化操作
    2. 求出来p比2^k还要大时(后面一共只有2^k个数可以取,p不能取更多)要特判

    Program VijosP1315;
    const s=100000000;
    type x=record
    l:array[0..25] of longint;
    end;
    var
    w,k,p,r,i:longint;
    c:array[0..512,0..512] of x;
    c0,ans:x;

    procedure print(c:x);
    var i:longint;
    begin
    for i:=1 to 25 do if c.l[i]<>0 then break;
    write(c.l[i]);inc(i);
    for i:=i to 25 do begin
    if c.l[i]<10000000 then write(0);
    if c.l[i]<1000000 then write(0);
    if c.l[i]<100000 then write(0);
    if c.l[i]<10000 then write(0);
    if c.l[i]<1000 then write(0);
    if c.l[i]<100 then write(0);
    if c.l[i]<10 then write(0);
    write(c.l[i]);
    end;
    end;

    function add(x1,x2:x):x;
    var i:longint;
    begin
    for i:=1 to 25 do begin
    add.l[i]:=(x1.l[i]+x2.l[i]);
    end;
    for i:=25 downto 1 do begin
    add.l[i-1]:=add.l[i-1]+add.l[i] div s;
    add.l[i]:=add.l[i] mod s;
    end;
    end;

    procedure init;
    var i,j:longint;
    begin
    for i:=0 to 25 do c0.l[i]:=0;
    for i:=0 to 512 do
    for j:=0 to 512 do
    c[i,j]:=c0;
    c[1,1].l[25]:=1;
    for i:=1 to 512 do c[i,0]:=c[1,1];
    for i:=1 to 512 do begin
    for j:=1 to i do begin
    if c[i,j].l[25]=0 then c[i,j]:=add(c[i-1,j],c[i-1,j-1]);
    end;
    end;
    end;

    begin
    init;
    readln(k,w);
    p:=w div k;
    r:=w mod k;
    k:=1 shl k;
    if p>=k then begin
    p:=k;
    r:=0;
    end;
    ans:=c0;
    r:=(1 shl r)-1;
    for i:=2 to p do ans:=add(ans,c[k-1,i]);
    for i:=1 to r do ans:=add(ans,c[k-1-i,p]);
    print(ans);
    end.
    //处女题解多多指教

  • 0
    @ 2017-10-04 13:33:32
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    using namespace std;
    
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    struct bigint
    {
        vector<int> num;
        int operator == (bigint b)
        {
            if (num.size()!=b.num.size())
                return 0;
            else
            {
                for (unsigned long long i=0,size=num.size();i<size;i++)
                    if (num[i]!=b.num[i])
                        return 0;
                return 1;
            }
        }
        int operator != (bigint b)
        {
            return ((!(*this==b))?1:0);
        }
        int operator < (bigint b)
        {
            if (num.size()<b.num.size())
                return 1;
            else if (num.size()>b.num.size())
                return 0;
            else
            {
                for (unsigned long long i=0,size=num.size();i<size;i++)
                {
                    if (num[size-1-i]<b.num[size-1-i])
                        return 1;
                    else if (num[size-1-i]>b.num[size-1-i])
                        return 0;
                }
                return 0;
            }
        }
        int operator > (bigint b)
        {
            return ((!(*this<b)&&!(*this==b))?1:0);
        }
        int operator <= (bigint b)
        {
            return ((!(*this>b))?1:0);
        }
        int operator >= (bigint b)
        {
            return ((!(*this<b))?1:0);
        }
        bigint mov(long long x)
        {
            bigint ans;
            ans.num.clear();
            ans.num.resize(num.size()+x);
            for (long long i=0,size=num.size();i<size;i++)
                if (i+x>=0)
                    ans.num[i+x]=num[i];
            return ans;
        }
        bigint operator = (long long b)
        {
            char s[20+1];
            sprintf(s,"%lld",b);
            num.clear();
            num.resize(strlen(s));
            for (unsigned long long i=0,size=num.size();i<size;i++)
                num[i]=(s[size-1-i]-'0');
            return (*this);
        }
        bigint operator = (string b)
        {
            num.clear();
            num.resize(b.size());
            for (unsigned long long i=0,size=num.size();i<size;i++)
                num[i]=(b[size-1-i]-'0');
            return (*this);
        }
        bigint operator + (bigint b)
        {
            bigint ans;
            ans.num.clear();
            ans.num.resize(max(num.size(),b.num.size()));
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
                ans.num[i]=((i<num.size())?num[i]:0)+((i<b.num.size())?b.num[i]:0);
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
            return ans;
        }
        bigint operator += (bigint b)
        {
            return (*this=(*this+b));
        }
        bigint operator - (bigint b)
        {
            bigint ans;
            ans.num.clear();
            ans.num.resize(max(num.size(),b.num.size()));
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
                ans.num[i]=((i<num.size())?num[i]:0)-((i<b.num.size())?b.num[i]:0);
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
                while (ans.num[i]<0)
                    ans.num[i]+=10,ans.num[i+1]--;
            while (ans.num[ans.num.size()-1]==0)
                ans.num.resize(ans.num.size()-1);
            return ans;
        }
        bigint operator -= (bigint b)
        {
            return (*this=(*this-b));
        }
        bigint operator * (bigint b)
        {
            bigint ans,num_0;
            num_0=0;
            ans.num.clear();
            if (*this!=num_0&&b!=num_0)
            {
                ans.num.resize(num.size()+b.num.size()-1);
                for (unsigned long long i=0,size_1=num.size();i<size_1;i++)
                    for (unsigned long long j=0,size_2=b.num.size
    
    ();j<size_2;j++)
                        ans.num[i+j]+=(num[i]*b.num[j]);
                for (unsigned long long i=0,size=ans.num.size();i<size;i++)
                {
                    if (ans.num[i]>=10&&i==size-1)
                        ans.num.resize(++size);
                    ans.num[i+1]+=(ans.num[i]/10);
                    ans.num[i]%=10;
                }
            }
            else
                ans=0;
            return ans;
        }
        bigint operator *= (bigint b)
        {
            return (*this=(*this*b));
        }
        bigint operator / (bigint b)
        {
            bigint ans,num_0;
            num_0=0;
            ans.num.clear();
            if (*this!=num_0&&*this>num_0)
            {
                ans.num.resize(num.size());
                bigint x,y;
                x=*this,y=b.mov(num.size()-b.num.size());
                unsigned long long rec=0;
                for (unsigned long long ci=0,i=num.size()-1,temp=0;ci<=num.size()-
    
    b.num.size();ci++,rec=i,i-=temp)
                {
                    if (temp==0)
                    {
                        if (x>=y)
                            temp=1;
                    }
                    while (x>=y)
                        x-=y,ans.num[i]++;
                    y=y.mov(-1);
                }
                ans=ans.mov(-rec);
                for (unsigned long long i=0,size=ans.num.size();i<size;i++)
                {
                    if (ans.num[i]>=10&&i==size-1)
                        ans.num.resize(++size);
                    ans.num[i+1]+=(ans.num[i]/10);
                    ans.num[i]%=10;
                }
            }
            else if (*this!=num_0&&*this==num_0)
                ans=1;
            else
                ans=0;
            return ans;
        }
        bigint operator /= (bigint b)
        {
            return (*this=(*this/b));
        }
        void print()
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
                printf("%d",num[size-1-i]);
        }
    };
    
    int n,w;
    bigint ans;
    bigint c[(1<<9)+1][(1<<9)+1];
    
    int main()
    {
        while (~scanf("%d%d",&n,&w))
        {
            for (int i=0;i<=(1<<n);i++)
                for (int j=0;j<=(1<<n);j++)
                    c[i][j]=0;
            for (int i=1;i<=(1<<n);i++)
            {
                c[i][0]=c[i][i]=1;
                for (int j=1;j<i;j++)
                    c[i][j]=c[i-1][j-1]+c[i-1][j];
            }
            ans=0;
            for (int i=2;i<=w/n&&i<(1<<n);i++)
                ans+=c[(1<<n)-1][i];
            for (int i=1;i<(1<<(w%n))&&w/n<(1<<n)-i;i++)
                ans+=c[(1<<n)-i-1][w/n];
            ans.print();
            printf("\n");
        }
    }
    
  • 0
    @ 2015-09-25 19:44:21

    /*

    Author: Slience_K
    Belong: C++
    Pro: NOIP 2006 - 4

    */
    #include <cstdio>
    #include <algorithm>
    #define LL long long
    using namespace std;
    const int INF = ( int )( 1e9 );
    int c[ 600 ][ 600 ][ 50 ] , ans[ 50 ];
    int w , k;
    void Add( int a[] , int b[] , int z[] ){
    z[ 0 ] = max( a[ 0 ] , b[ 0 ] );
    for( int i = 1 ; i <= z[ 0 ] ; i++ ){
    z[ i ] += a[ i ] + b[ i ];
    z[ i + 1 ] += z[ i ] / INF;
    z[ i ] %= INF;
    }
    if ( z[ z[ 0 ] + 1 ] ) z[ 0 ]++;
    }
    void Plus( int a[] ){
    ans[ 0 ] = max( ans[ 0 ] , a[ 0 ] );
    for( int i = 1 ; i <= ans[ 0 ] ; i++ ){
    ans[ i ] += a[ i ];
    ans[ i + 1 ] += ans[ i ] / INF;
    ans[ i ] %= INF;
    }
    if ( ans[ ans[ 0 ] + 1 ] ) ans[ 0 ]++;
    }
    int main(){
    scanf( "%d%d" , &k , &w );
    c[ 1 ][ 0 ][ 1 ] = c[ 1 ][ 1 ][ 1 ] = 1;
    c[ 1 ][ 0 ][ 0 ] = c[ 1 ][ 1 ][ 0 ] = 1;
    for( int i = 2 ; i <= ( 1 << k ) ; i++ )
    for( int j = 0 ; j <= i ; j++ )
    if ( j == 0 ) c[ i ][ j ][ 0 ] = c[ i ][ j ][ 1 ] = 1;
    else Add( c[ i - 1 ][ j ] , c[ i - 1 ][ j - 1 ] , c[ i ][ j ] );
    for( int i = 2 ; i <= w / k ; i++ )
    Plus( c[ ( 1 << k ) - 1 ][ i ] );
    for( int i = 1 ; i <= ( 1 << ( w % k ) ) - 1 ; i++ )
    Plus( c[ ( 1 << k ) - i - 1 ][ w / k ] );
    printf( "%d" , ans[ ans[ 0 ] ] );
    for( int i = ans[ 0 ] - 1 ; i >= 1 ; i-- )
    printf( "%09d" , ans[ i ] );
    return 0;
    }

  • 0
    @ 2015-09-16 23:10:50

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 109 ms, mem = 231152 KiB, score = 10
    测试数据 #1: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
    测试数据 #2: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
    测试数据 #3: Accepted, time = 93 ms, mem = 231144 KiB, score = 10
    测试数据 #4: Accepted, time = 93 ms, mem = 231148 KiB, score = 10
    测试数据 #5: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
    测试数据 #6: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
    测试数据 #7: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
    测试数据 #8: Accepted, time = 78 ms, mem = 231152 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 231152 KiB, score = 10
    Accepted, time = 931 ms, mem = 231152 KiB, score = 100

    高精度+预处理组合数计算(帕斯卡公式)
    。。。其实几乎所有时间都是预处理,不过可以压下位,懒得写了(其实也没写过)

    • @ 2015-09-16 23:13:15

      貌似其他人都不是预处理的

  • 0
    @ 2015-08-09 11:54:44

    组合+高精
    #include <iostream>
    #include <cstdio>
    using namespace std;

    int c[512][512][100];
    void plus1(int x[],int y[],int z[]){

    z[0]=max(x[0],y[0]);
    for(int i=1;i<=z[0];i++)
    {
    z[i]+=x[i]+y[i];
    z[i+1]+=z[i]/10;
    z[i]%=10;

    }

    if(z[z[0]+1]!=0)z[0]++;

    }
    void plus2(int x[],int y[])
    {
    x[0]=max(x[0],y[0]);
    for(int i=1;i<=x[0];i++)
    {
    x[i]+=y[i];
    x[i+1]+=x[i]/10;
    x[i]%=10;

    }

    if(x[x[0]+1]!=0)x[0]++;
    }

    int main(){
    int k,n,bmax,hmax,ans[201]={0};
    cin>>k>>n;
    bmax=1<<k;
    hmax=1<<(n%k);
    c[0][0][0]=c[0][0][1]=1;
    for(int i=1;i<bmax;i++)
    for(int j=0;j<=i;j++)
    {
    if(j==0)c[i][j][0]=c[i][j][1]=1;
    else plus1(c[i-1][j],c[i-1][j-1],c[i][j]);
    }
    for(int i=2;i<=n/k&&i<bmax;i++)plus2(ans,c[bmax-1][i]);
    for(int i=1;i<hmax&&n/k+i<bmax;i++)plus2(ans,c[bmax-i-1][n/k]);
    for(int i=ans[0];i>=1;i--)printf("%d",ans[i]);

    return 0;
    }

  • 0
    @ 2015-03-04 23:18:52

    Block code

    #include <cstdio>
    #include <cmath>
    #include <cstring>
    using namespace std;
    struct num{
    int len, a[210];
    num(int x = 0) {
    len = 0;
    memset(a, 0, sizeof(a));
    while (x) {
    a[++len] = x % 10;
    x /= 10;
    }
    }
    void print() {
    for (int i = len; i > 0; i--) printf("%d", a[i]); printf("\n");
    }
    } c;
    num operator * (const num & a, int b) {
    c = num(0);
    for (int i = 1; i <= a.len || c.a[i] != 0; i++) {
    c.a[i] += a.a[i]*b;
    c.a[i+1] += c.a[i] / 10;
    c.a[i] %= 10;
    c.len = i;
    }
    return c;
    }
    num operator / (const num & a, int b) {
    c = a;
    for (int i = a.len; i > 0; i--) {
    c.a[i-1] += c.a[i] % b * 10;
    c.a[i] /= b;
    }
    while (c.a[c.len] == 0) c.len--;
    return c;
    }
    num operator - (const num & a, const num & b) {
    c = a;
    for (int i = 1; i <= a.len; i++) {
    c.a[i] -= b.a[i];
    if (c.a[i] < 0) c.a[i] += 10, c.a[i+1]--;
    }
    while (c.a[c.len] == 0) c.len--;
    return c;
    }
    num operator + (const num & a, const num & b) {
    c = num(0);
    for (int i = 1; i <= a.len || i <= b.len || c.a[i] != 0; i++) {
    c.a[i] += a.a[i]+b.a[i];
    c.a[i+1] += c.a[i] / 10;
    c.a[i] %= 10;
    c.len = i;
    }
    return c;
    }
    int main() {
    freopen("2knum.in", "r", stdin);
    freopen("2knum.out", "w", stdout);
    int k, w;
    scanf("%d%d", &k, &w);
    num t, ans(0);
    int m = (1<<k)-1;
    t = num(m);
    for (int i = 2; i <= (w/k)+1; i++) {
    t = t * (--m) / i;
    ans = ans + t;
    // ans.print();
    }
    m = (1<<k) - (1<<(w%k));
    t = num(m);
    for (int i = 2; i <= (w/k)+1; i++) t = t * (--m) / i;
    // t.print();
    ans = ans - t;
    ans.print();
    return 0;
    }

  • 0
    @ 2015-03-04 23:16:11

    #include <cstdio>
    #include <cmath>
    #include <cstring>
    using namespace std;
    struct num{
    int len, a[210];
    num(int x = 0) {
    len = 0;
    memset(a, 0, sizeof(a));
    while (x) {
    a[++len] = x % 10;
    x /= 10;
    }
    }
    void print() {
    for (int i = len; i > 0; i--) printf("%d", a[i]); printf("\n");
    }
    } c;
    num operator * (const num & a, int b) {
    c = num(0);
    for (int i = 1; i <= a.len || c.a[i] != 0; i++) {
    c.a[i] += a.a[i]*b;
    c.a[i+1] += c.a[i] / 10;
    c.a[i] %= 10;
    c.len = i;
    }
    return c;
    }
    num operator / (const num & a, int b) {
    c = a;
    for (int i = a.len; i > 0; i--) {
    c.a[i-1] += c.a[i] % b * 10;
    c.a[i] /= b;
    }
    while (c.a[c.len] == 0) c.len--;
    return c;
    }
    num operator - (const num & a, const num & b) {
    c = a;
    for (int i = 1; i <= a.len; i++) {
    c.a[i] -= b.a[i];
    if (c.a[i] < 0) c.a[i] += 10, c.a[i+1]--;
    }
    while (c.a[c.len] == 0) c.len--;
    return c;
    }
    num operator + (const num & a, const num & b) {
    c = num(0);
    for (int i = 1; i <= a.len || i <= b.len || c.a[i] != 0; i++) {
    c.a[i] += a.a[i]+b.a[i];
    c.a[i+1] += c.a[i] / 10;
    c.a[i] %= 10;
    c.len = i;
    }
    return c;
    }
    int main() {
    int k, w;
    scanf("%d%d", &k, &w);
    num t, ans(0);
    int m = (1<<k)-1;
    t = num(m);
    for (int i = 2; i <= (w/k)+1; i++) {
    t = t * (--m) / i;
    ans = ans + t;
    // ans.print();
    }
    m = (1<<k) - (1<<(w%k));
    t = num(m);
    for (int i = 2; i <= (w/k)+1; i++) t = t * (--m) / i;
    // t.print();
    ans = ans - t;
    ans.print();
    return 0;
    }

  • 0
    @ 2014-11-02 00:17:41

    #include <iostream>
    #include <cstring>
    #include <string>
    #include <cstdio>
    #include <sstream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int maxw=30001;
    const int maxk=1025;
    #include <vector>
    #include <string>
    #include <sstream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    struct BigInteger
    {
    static const int BASE=100000000;
    static const int WIDTH=8;
    vector<int> s;

    BigInteger(long long num=0) {*this=num;}
    BigInteger operator = (long long num)
    {
    s.clear();
    do
    {
    s.push_back(num%BASE);
    num/=BASE;
    }while(num>0);
    return *this;
    }
    BigInteger operator = (const string& str)
    {
    s.clear();
    int x,len=(str.length()-1)/WIDTH+1;
    for(int i=0;i<len;i++)
    {
    int end=str.length()-i*WIDTH;
    int start=max(0,end-WIDTH);
    sscanf(str.substr(start,end-start).c_str(),"%d",&x);
    s.push_back(x);
    }
    return *this;
    }

    bool operator < (const BigInteger& b) const
    {
    if(s.size()!=b.s.size()) return s.size()<b.s.size();
    for(int i=s.size()-1;i>=0;i--)
    if(s[i]!=b.s[i]) return s[i]<b.s[i];
    return false;
    }

    BigInteger operator + (const BigInteger& b) const
    {
    BigInteger c;
    c.s.clear();
    for(int i=0,g=0;;i++)
    {
    if(g==0 && i>=s.size() && i>=b.s.size()) break;
    int x=g;
    if(i<s.size()) x+=s[i];
    if(i<b.s.size()) x+=b.s[i];
    c.s.push_back(x%BASE);
    g=x/BASE;
    }
    return c;
    }

    BigInteger operator - (const BigInteger& b) const

    {
    BigInteger c;
    c.s.clear();
    for(int i=0,g=0;;i++)
    {
    if(g==0 && i>=s.size() && i>=b.s.size()) break;
    int x=s[i]+g;
    if(i<b.s.size())
    {
    x-=b.s[i];
    if(x<0) {x+=10; g=-1;} else g=0;
    }
    c.s.push_back(x%BASE);
    }
    return c;
    }

    BigInteger operator += (const BigInteger& b)
    {
    *this=*this+b; return *this;
    }
    };
    ostream& operator << (ostream &out, const BigInteger& x)
    {
    out<<x.s.back();
    for(int i=x.s.size()-2;i>=0;i--)
    {
    char buf[20];
    sprintf(buf,"%08d",x.s[i]);
    for(int j=0;j<strlen(buf);j++) out<<buf[j];
    }
    return out;
    }
    istream& operator >> (istream &in, BigInteger&x)
    {
    string s;
    if(!(in>>s)) return in;
    x=s;
    return in;
    }
    int k,w;
    BigInteger c[maxw][maxk];
    int main()
    {
    scanf("%d %d",&k,&w);
    int q=1<<k,n=min(w/k,q-2),m=w%k;
    c[0][0]=1; c[1][0]=1; c[0][1]=1; c[1][1]=1;
    for(int i=2;i<=q;i++)
    {
    c[i][0]=1;
    for(int j=1;j<=i;j++)
    c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    BigInteger ans=0;
    for(int i=2;i<=n+1;i++)
    ans+=c[q-1][i];
    ans=ans-c[q-(1<<m)][n+1];
    cout<<ans;
    return 0;
    }

  • 0
    @ 2014-10-24 21:29:01

    var
    i,j,n,m,x,y,z,l,k:longint;o:int64;flag:boolean;
    a:array[-1..1,1..520,1..25]of longint;
    procedure jia(e,f,g,h:longint); var i:longint;
    begin for i:=1 to 25 do a[e,f,i]:=a[e,f,i]+a[g,h,i];
    for i:=1 to 25 do if a[e,f,i]>=100000000 then begin
    a[e,f,i+1]:=a[e,f,i+1]+a[e,f,i]div 100000000;
    a[e,f,i]:=a[e,f,i]mod 100000000;end;end;
    procedure clear(e,f:longint); var i:longint;
    begin for i:=1 to 25 do a[e,f,i]:=0;end;
    procedure cop(e,f,g,h:longint);var i:longint;
    begin for i:=1 to 25 do a[e,f,i]:=a[g,h,i];end;
    function fu(e:longint):longint;
    begin if e=y then exit(x);exit(z-i);end;
    begin
    readln(n,m); z:=1;for i:=1 to n do z:=2*z;dec(z);
    x:=1;for i:=1 to m mod n do x:=2*x;dec(x);
    if m mod n=0 then x:=z;
    if m mod n<>0 then y:=m div n+1 else y:=m div n;if y>z then y:=z;
    for i:=1 to z do a[0,i,1]:=1;
    for i:=2 to y do begin l:=l xor 1;
    clear(l,z-i+1);jia(l,z-i+1,l xor 1,z-i+2);
    if z-i<=fu(i) then jia(-1,1,l xor 1,z-i+2);
    for j:=z-i downto 1 do begin cop(l,j,l,j+1);jia(l,j,l xor 1,j+1);
    if j<=fu(i) then jia(-1,1,l,j);end;end;
    for i:=25 downto 1 do if flag or(a[-1,1,i]<>0) then begin
    if flag then for j:=1 to 8 do begin o:=a[-1,1,i];
    for k:=1 to j do o:=o*10;if o<100000000 then write('0')else break;end;
    write(a[-1,1,i]);flag:=true;end;
    end.
    可以将数组压缩
    FROM ADAM

  • 0
    @ 2013-08-27 13:32:09

    const py=1000000;
    type dd=array[0..35] of longint;
    var
    k,w,m,i,m1:longint;
    f:array[0..513,0..513] of dd;
    ans:dd;
    function add(a,b:dd):dd;
    var i,len:longint;
    begin
    fillchar(add,sizeof(add),0);
    if a[0]>b[0] then len:=a[0]
    else len:=b[0];
    for i:=1 to len do
    begin
    add[i]:=add[i]+a[i]+b[i];
    add[i+1]:=add[i] div py;
    add[i]:=add[i] mod py;
    end;
    if add[len+1]>0 then inc(len);
    add[0]:=len;
    end;
    procedure c(n:longint);
    var i,j:longint;
    begin
    fillchar(f,sizeof(f),0);
    f[0,0][0]:=1; f[0,0][1]:=1;
    for i:=1 to n do
    for j:=0 to i do
    if j=0 then begin f[i,j][0]:=1; f[i,j][1]:=1; end
    else f[i,j]:=add(f[i-1,j-1],f[i-1,j]);
    // exit(f[n,m]);
    end;
    function min(a,b:longint):longint;
    begin
    if a>b then exit(b)
    else exit(a);
    end;

    begin
    readln(k,w);
    m:=1; for i:=1 to k do m:=m*2; m:=m-1;

    c(m);
    for i:=2 to min(m,w div k) do
    ans:=add(ans,f[m,i]);
    m1:=1;
    for i:=1 to w mod k do
    m1:=m1*2;
    m1:=m1-1;
    for i:=1 to m1 do
    ans:=add(ans,f[m-i,min(m,w div k)]);
    write(ans[ans[0]]);
    for i:=ans[0]-1 downto 1 do
    begin
    if ans[i]<10 then write('0');
    if ans[i]<100 then write('0');
    if ans[i]<1000 then write('0');
    if ans[i]<10000 then write('0');
    if ans[i]<100000 then write('0');
    write(ans[i]);
    end;
    end.

  • 0
    @ 2010-07-17 09:48:09

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 649ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:649ms

    递推+滚动数组+压位高精

    f表示第I位上为J时进制数的个数,具体自己想...

  • 0
    @ 2009-11-10 14:19:13

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 9ms

    ├ 测试数据 09:答案正确... 728ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    递推+滚动数组+压位高精加。。

    滚动数组其实根本不会写- -||||

  • 0
    @ 2009-11-07 15:55:04

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:9ms

  • 0
    @ 2009-11-03 17:51:27

    强大的评测机。。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-10-29 20:42:13

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    直接用公式算秒杀。。。

    ans:=C(m,i)(2

  • 0
    @ 2009-10-23 13:22:55

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 150ms

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:150ms

    ~~

    过不去~

  • 0
    @ 2009-10-07 22:33:21

    差距这么大.......

    sunny:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 509ms

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:509ms

    puppy:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 197ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:253ms

    让我很无语啊

  • 0
    @ 2009-09-18 02:00:33

    f表示有i位数字,最高位与最低位差小于j的符合条件的总数.

    f有两部分组成,

    一个是f,因为定义里面是小于j

    另一个就是f,

    这就相当于少用一个数字,少了数字,差就必然少1

    所以f=f+f

    边界条件

    f=1

    f[1,i]=i+1

    最终答案只要分两部分来求,

    除掉不能被k整除的最高位,设其为p,该位最大为q

    另一部分是能被整除的剩下几位.

    对于后者,求和f (i

  • 0
    @ 2009-08-26 00:27:13

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

信息

ID
1315
难度
5
分类
组合数学 | 数论 点击显示
标签
递交数
1413
已通过
516
通过率
37%
被复制
12
上传者