对超长正整数的处理？ - 编程论坛

#2

rjsp2022-03-23 21:37

第一步。n位的整数，各位之和最小是1，最大是9n。
100位的整数，各位之和最大才是900。
前缀从1遍历到900。

第二步。假设100位的整数各位之和是199，199-1-9-9=180，也就是说后97位之和是180。
后97位中有a个9，b个8，c个7，……，通过循环算出每个组合。

第三步。a个9，b个8，c个7，…… 一共可以组成 97! / a! / b! / c! / ...... 种不同的97位数。

看起来最后一步有问题，数值太大，我得再想想

#3

rjsp2022-03-24 22:04

第三步的计算，只需要记录1到97这97个数中每一个数的因子和数目，然后乘就是因子数目想加，除就是因子数目相减。
最后所有留下的因子相乘，乘的过程中，中间结果不停地模除 10^9+7 以避免溢出

#4

纯蓝之刃2022-03-25 10:56

我先来一个，不知道有没有bug，仅供参考。

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print_value(int count,int current_len,const char *a)
{
    char c_str[]={1,0,0,0,0,0,0,0,0,7},c_len,ch;
    char b[110];
    int i,j,offset=0;

    c_len=sizeof(c_str);
    memset(b,0,sizeof(b));
    printf("%d ",count);
    for(i=current_len-1,j=0;i>=0;i--)
    {
        printf("%d",a[i]);
        b[j++]=a[i];
    }

    while(1)
    {
        if(offset>current_len-c_len)
            break;

        if(memcmp(b+offset,c_str,c_len)>=0)
        {
            for(i=c_len-1+offset,ch=0;i>=0+offset;i--)
            {
                ch=ch+b[i]-c_str[i-offset];
                if(ch>=0)
                {
                    b[i]=ch;
                    ch=0;
                }
                else
                {
                    b[i]=ch+10;
                    ch=-1;
                }
            }
            for(i=0;i<current_len;i++)
            {
                if(b[i]!=0)
                {
                    offset=i;
                    break;
                }
            }
        }
        else
        {
            break;
        }
    }
    printf(" ");
    for(i=offset;i<current_len;i++)
    {
        printf("%d",b[i]);
    }
    printf("\n");
}

int main()
{
    char a[100],b[5];
    int i,j,n,sum,count=0,current_bit=0,current_len;

    printf("请输入一个正整数(长度大于0，小等于100):");
    scanf("%u",&n);

    memset(a,0,sizeof(a));
    current_len=1;

    while(1)
    {
        for(i=0;i<=9;i++)
        {
            a[current_bit]=i;

            for(j=0,sum=0;j<current_len;j++)
                sum+=a[j];

            memset(b,0,sizeof(b));
            sprintf(b,"%d",sum);
            for(j=0;j<strlen(b);j++)
            {
                if(b[j]!=a[current_len-j-1]+'0')
                    break;
            }
            if(j==strlen(b) && a[current_len-1]!=0)
            {
                count++;
                print_value(count,current_len,a);
            }
        }

        while(1)
        {
            if(a[current_bit]<9)
            {
                a[current_bit]++;
                current_bit=0;
                break;
            }
            else
            {
                current_bit++;
                if(current_bit>=current_len)
                {
                    current_len++;
                    current_bit=0;
                    memset(a,0,sizeof(a));
                    break;
                }
            }
        }
        if(current_len>n)
            break;
    }

    return 0;
}

[此贴子已经被作者于2022-3-25 11:01编辑过]

#5

rjsp2022-03-25 15:08

回复 4楼纯蓝之刃

如果是 3位数 abc，
那么 a+b+c = a 或 a+b+c = 10a+b
前者解出来是 b=0 && c=0，也就是 100、200、300、……、900
后者解出来是 a=1 && c=9，也就是 109、119、129、……、199
一共19个

#6

rjsp2022-03-25 15:25

f(1)=10
f(2)=9
f(3)=19
f(4)=119
f(5)=1119
f(6)=11119
……
看来，规律性很强，只要再模除 10^9+7 就行了

#7

纯蓝之刃2022-03-26 14:29

回复 5楼 rjsp

之前的有bug，改了一下，感觉应该差不多了。

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print_value(int count,int current_len,const char *a)
{
    char c_str[]={1,0,0,0,0,0,0,0,0,7},c_len,ch;
    char b[110];
    int i,j,offset=0;

    c_len=sizeof(c_str);
    memset(b,0,sizeof(b));
    printf("%d ",count);
    for(i=current_len-1,j=0;i>=0;i--)
    {
        printf("%d",a[i]);
        b[j++]=a[i];
    }

    while(1)
    {
        if(offset>current_len-c_len)
            break;

        if(memcmp(b+offset,c_str,c_len)>=0)
        {
            for(i=c_len-1+offset,ch=0;i>=0+offset;i--)
            {
                ch=ch+b[i]-c_str[i-offset];
                if(ch>=0)
                {
                    b[i]=ch;
                    ch=0;
                }
                else
                {
                    b[i]=ch+10;
                    ch=-1;
                }
            }
            for(i=0;i<current_len;i++)
            {
                if(b[i]!=0)
                {
                    offset=i;
                    break;
                }
            }
        }
        else
        {
            break;
        }
    }
    printf(" ");
    for(i=offset;i<current_len;i++)
    {
        printf("%d",b[i]);
    }
    printf("\n");
}

int main()
{
    char a[100],b[5];
    int i,j,k,n,sum,count=0,current_bit=0,current_len,count_temp=0;

    printf("请输入一个正整数(长度大于0，小等于100):");
    scanf("%u",&n);

    memset(a,0,sizeof(a));
    current_len=1;

    while(1)
    {
        for(i=0;i<=9;i++)
        {
            a[current_bit]=i;

            for(j=0,sum=0;j<current_len;j++)
                sum+=a[j];

            memset(b,0,sizeof(b));
            sprintf(b,"%d",sum);
            for(j=0;j<strlen(b);j++)
            {
                if(b[j]!=a[current_len-j-1]+'0')
                    break;
            }
            if(j==strlen(b) && a[current_len-1]!=0)
            {
                count++;
                print_value(count,current_len,a);
            }
        }

        while(1)
        {
            if(a[current_bit]<9)
            {
                a[current_bit]++;
                for(i=0;i<current_bit;i++)
                    a[i]=0;
                current_bit=0;
                break;
            }
            else
            {
                current_bit++;
                if(current_bit>=current_len)
                {
                    current_len++;
                    current_bit=0;
                    memset(a,0,sizeof(a));
                    a[current_len-1]=1;
                    break;
                }
            }
        }
        if(current_len>n)
            break;
    }

    return 0;
}

#8

逢考必过阿俊2022-03-27 17:07

回复 6楼 rjsp

谢谢你！如果能找到规律就太好了！
不过，我按照这种规律解题，提交结果显示是wrong answer(部分错误)。
请问，我的程序是哪里出错了呢？

#include <stdio.h>
#include <math.h>
int main()
{
    int n = 0;
    unsigned long long m = 0;
    scanf("%d", &n);

    if (n == 1)
    {
        m = 10;
    }
    else if (n == 2)
    {
        m = 9;
    }
    else
    {
        m = 9;
        for (int i = 1; i <= n - 2; ++i)
        {
            m += (int)pow(10, i);
            m = m % ((int)pow(10, 9) + 7);
        }
    }

    printf("%llu\n", m);
    return 0;
}

#9

逢考必过阿俊2022-03-27 17:16

回复 7楼纯蓝之刃

谢谢你！写了好长的代码，辛苦你了！
不过，rjsp回复说这道题的答案是有规律的，我想试试用规律输出答案。

#10

逢考必过阿俊2022-03-27 17:40

回复 8楼逢考必过阿俊

出错原因应该是：m在取模之前就已经溢出

我把for循环改了一下
for (int i = 1; i <= n - 2; ++i)
        {
            m += (int)pow(10, i) % ((int)pow(10, 9) + 7);
        }

f(11)之后的结果仍然是错误的，为什么呀？

[此贴子已经被作者于2022-3-27 17:57编辑过]

#11

rjsp2022-03-29 16:56

回复 9楼逢考必过阿俊

我只是这么一说，只能可能有规律。但既然你说了，我就写段代码试试，发现没规律

代码没验证，写得也很烂，只是为了验证有没有规律

程序代码：

#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long ST;

ST bar( unsigned p, unsigned n9, unsigned n8, unsigned n7, unsigned n6, unsigned n5, unsigned n4, unsigned n3, unsigned n2, unsigned n1 )
{
    static const unsigned primes[25] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
    static unsigned table[100][25] = { 1 };
    if( table[0][0] == 1 )
    {
        table[0][0] = 0;
        for( unsigned r=0; r!=100; ++r )
        {
            unsigned t = r;
            for( unsigned i=0; i!=25 && t!=0; )
            {
                if( t%primes[i] == 0 )
                {
                    t /= primes[i];
                    ++table[r][i];
                }
                else
                    ++i;
            }
        }
        for( unsigned r=1; r!=100; ++r )
        {
            for( unsigned i=0; i!=25; ++i )
                table[r][i] += table[r-1][i];
        }
    }

    // p! / n9! / n8! / …… / n0!
    unsigned n0 = p - n9 - n8 - n7 - n6 - n5 - n4 - n3 - n2 - n1;
    unsigned row[25] = { 0 };
    for( unsigned i=0; i!=25; ++i )
        row[i] = table[p][i]-table[n9][i]-table[n8][i]-table[n7][i]-table[n6][i]-table[n5][i]-table[n4][i]-table[n3][i]-table[n2][i]-table[n1][i]-table[n0][i];

    ST result = 1;
    for( unsigned i=0; i!=25; ++i )
    {
        for( unsigned j=0; j!=row[i]; ++j )
        {
            if( result*primes[i]/result!=primes[i] )
            {
                puts( "--- overflow ---" );
                exit(1);
            }
            result *= primes[i];
        }
    }
    return result;
}

ST foo( unsigned n )
{
    ST result = 0;

    // n位整数，各位之和最大为9n，也就是前缀在[1,9n]范围内
    for( unsigned pre=1; pre<=9*n; ++pre )
    {
        const unsigned p = 1 + (pre>=10) + (pre>=100); // pre一共有几位
        const unsigned r = n-p; // 剩余的位数
        const unsigned s = pre - pre/1%10 - pre/10%10 - pre/100%10; // 剩余的位数的各位和
        if( s > r*9 )
            break;

        // 现在要求剩余的位数的各位之和s 等于前缀的值pre - 前缀的各位之和
        // 例如 23981（前缀23），(9+8+1) == 23 - (2+3)
        // 设剩余的位数有a个9，b个8，c个7，……(a+b+c+…<=r && 9a+8b+7c+…==s)
        for( unsigned a=0; a<=r && a*9<=s; ++a )
        for( unsigned b=0; a+b<=r && a*9+b*8<=s; ++b )
        for( unsigned c=0; a+b+c<=r && a*9+b*8+c*7<=s; ++c )
        for( unsigned d=0; a+b+c+d<=r && a*9+b*8+c*7+d*6<=s; ++d )
        for( unsigned e=0; a+b+c+d+e<=r && a*9+b*8+c*7+d*6+e*5<=s; ++e )
        for( unsigned f=0; a+b+c+d+e+f<=r && a*9+b*8+c*7+d*6+e*5+f*4<=s; ++f )
        for( unsigned g=0; a+b+c+d+e+f+g<=r && a*9+b*8+c*7+d*6+e*5+f*4+g*3<=s; ++g )
        for( unsigned h=0; a+b+c+d+e+f+g+h<=r && a*9+b*8+c*7+d*6+e*5+f*4+g*3+h*2<=s; ++h )
        {
            const unsigned i_max = r-a-b-c-d-e-f-g-h;
            const unsigned i = s-a*9-b*8-c*7-d*6-e*5-f*4-g*3-h*2;
            if( i <= i_max )
            {
                ST the = bar( r, a,b,c,d,e,f,g,h,i );
                if( result+the<result )
                {
                    puts( "--- overflow ---" );
                    exit(1);
                }
                result += the;
            }
        }
    }

    return result;
}

int main( void )
{
    for( unsigned n=1; n<=100; ++n )
        printf( "f(%u) = %llu\n", n, foo(n) );
}

输出是

f(1) = 9 // 这个还要加1，因为0也是1位数
f(2) = 9
f(3) = 19
f(4) = 119
f(5) = 1119
f(6) = 11119
f(7) = 111119
f(8) = 1111119
f(9) = 11111119
f(10) = 111111119
f(11) = 1111111119
f(12) = 11111111109 // 这里就没规律了，不知道是真如此，还是我代码有bug
f(13) = 111110187329
f(14) = 1110772528459
f(15) = 11077860489819
f(16) = 109455801519569
f(17) = 1057665543096469
f(18) = 9838457914487439
f(19) = 86933146186369559
f(20) = 724511714337673129
f(21) = 5699633355881508969
--- overflow ---

#12

逢考必过阿俊2022-04-03 13:30

回复 11楼 rjsp

是的，f（12）之后就不一样了。
谢谢你的解答，这是题目解析：

只有本站会员才能查看附件，请登录

#13

rjsp2022-04-03 20:23

回复 12楼逢考必过阿俊

用这种dp的方法，你求 100位花酒数用了多长时间？
我觉得应该非常非常耗时，是个不可能完成的任务

#14

rjsp2022-04-05 01:07

按照你图中所说的方法，根本算不到 100位花酒数，因为速度太慢太慢，我猜一百年都算不完。

然后我使用二分法测试了一下，一分钟内就算出来了。
但因为是用于“测试”的代码，所以代码质量不高，懒得优化了；
其二，我算的是真实的结果，而不是模除10^9+7的结果，如果是要模除10^9+7的结果，那不需要使用“大整数”类型，简单太多
其三，为了方便，用了C++代码，但算法本身很简单，看 bar10 那个函数，二分 + 缓存

输出结果

f(1) = 10
f(2) = 9
f(3) = 19
f(4) = 119
f(5) = 1119
f(6) = 11119
f(7) = 111119
f(8) = 1111119
f(9) = 11111119
f(10) = 111111119
f(11) = 1111111119
f(12) = 11111111109
f(13) = 111110187329
f(14) = 1110772528459
f(15) = 11077860489819
f(16) = 109455801519569
f(17) = 1057665543096469
f(18) = 9838457914487439
f(19) = 86933146186369559
f(20) = 724511714337673129
f(21) = 5699633355881508969
f(22) = 42732547304236063119
f(23) = 311435118084081470069
f(24) = 2274875985698024116119
f(25) = 17281272144757935903979
f(26) = 140656455164657673754359
f(27) = 1235898415534641441477979
f(28) = 11548484662122494343577619
f(29) = 112123605048388530792813559
f(30) = 1109873745939628739883820919
f(31) = 11075268343960057500078536429
f(32) = 110810069000375684685398829579
f(33) = 1109228715814449635940275475819
f(34) = 11102989733542989026759831263939
f(35) = 111154973888717987326857324140979
f(36) = 1113833716599296210722955485042139
f(37) = 11187178971262051395193710711270089
f(38) = 112863161482038794847067352523857139
f(39) = 1146811717218838521080991340187372209
f(40) = 11768833103533783341852908133119006969
f(41) = 122208270575190491410559683507573892169
f(42) = 1284323910739035393283305896784699057139
f(43) = 13634320046291145845490626219456926396609
f(44) = 145684219089375978833499939152652492437879
f(45) = 1559898736033334585406965093861495867153839
f(46) = 16666666691482800859080708121867483474079669
f(47) = 177099730902286894302005251813742346078439499
f(48) = 1867534974389747941684083234640786169440117099
f(49) = 19524190396714896567614194304956133162470902249
f(50) = 202357239848122475253129890477125678078474058199
f(51) = 2080607722711265593525955253420083143485317164999
f(52) = 21244773377916535187473270032536809464270616931349
f(53) = 215702370099089301456580390705337652194125719749149
f(54) = 2180565300251541700638052540598362430701653578666269
f(55) = 21976003696750355791577415972697736695188298544528909
f(56) = 221065126909457345047487647254475944983662606206327749
f(57) = 2222222222222223755940190130797926523628059388010506279
f(58) = 22348116408683052447794078416167180727916316650235524929
f(59) = 225091137779919838244336931916864922149762557101363227599
f(60) = 2272938635202600777666158535598071273400419976759816370939
f(61) = 23030771871667209033101168557051583097529391762967852881329
f(62) = 234304371737976902744396755727006662132800001526341177358889
f(63) = 2393830021194442566392616503328158524568480703452477464945489
f(64) = 24554907888914465629444103882562118271562090779899301377439879
f(65) = 252704293063848188584558444470292742165666295451255910851000539
f(66) = 2606517074222659389360630746338002394924128102554894783832576759
f(67) = 26911636636024223791928968382259638021797559293101440584859495959
f(68) = 277777777777777777777799122234010920002155943872016845943175058949
f(69) = 2863080266382609669533238242915567471574975042742393457067344250699
f(70) = 29440849129281957749739262119949838339812113457982078499216552215059
f(71) = 301839215202321616734283301502658200862687992813762236385057749877699
f(72) = 3084373644098863628797186851225757918579667414150065075374279767761719
f(73) = 31412400578082857908986197927971633252546788396215613509507469120323369
f(74) = 318900836826231370754751883191125795301135197602049984532771423111266869
f(75) = 3228399309016450245376986348506098415550532122717946959429557443133174529
f(76) = 32606986555023406402940593035033041520597170409978337745083851136856261409
f(77) = 328760965417198002219234633595367600231555804268312909534510135062309480769
f(78) = 3311112318485135579338724122411812369679637687722058702406732107073415788369
f(79) = 33333333333333333333333333333432715687424916769921811222856095442442905563019
f(80) = 335642197629403803027345878204235743592978856102713052113995693315494901027979
f(81) = 3382424983322445483888753301056851981009046490809486350261862630630384311206059
f(82) = 34131566510382926750634241362952964897216461461130590729275436793882492453065039
f(83) = 345006771983336819694111115903318259400943863285603520443662508699716341186175759
f(84) = 3494124603715797176216993700813110787363875122651644856325257197615358008883347529
f(85) = 35457161172811549647542459594466079904243095664800957936215045051976477821423611189
f(86) = 360460572766625126455552067646084779832252733836848264084787104830178886815327608879
f(87) = 3669942866221006490589584665579265993757807787569339301603237535185726431262813900219
f(88) = 37403380329148478214383041833500645027698411841248201281682419609993177317512894191899
f(89) = 381399566844435637299004859047842433136823299393740922138381783134004200697833741094659
f(90) = 3888888888888888888888888888888888889086840236722131309119591193760907189892379673026189
f(91) = 39629536043801023009416295524605361291040622708660580888623723248127534067155290642041869
f(92) = 403427762633902167042831083427087524350177447778130063365250683369092517105717930735641189
f(93) = 4101263107739473522474865527576954329237233282741174865050337033439400756496643790390312969
f(94) = 41627468751743625267467421110898812583365267172074055528905465227598638491063868462801790789
f(95) = 421807102703245534844877784251857854296524112217208946529714871289435976540907171444321996569
f(96) = 4267103644739676514079790438094192786221668666509345898095862361788759372167741643866258100549
f(97) = 43102151210578545676528847399650369373515475039055422290260568700122979090957164072955689979939
f(98) = 434821876602140569391166107951083935613514362501625171773301876118352043265385846933361217609289
f(99) = 4382285144929655001774920383437176228745710360853647734714624396041039918654870877647056001066839
f(100) = 44138387830958246546542989207604283153494099884534901818474997351534317207318004127537977354989029

程序代码：

#include <stdio.h>
#include <vector>
#include <map>
#include <string>
#include <cassert>

class Fuck
{
public:
    Fuck( unsigned maxval )
    {
        auto 是素数吗 = []( unsigned n )
        {
            if( n == 2 ) return true;
            if( n<2 || n%2==0  ) return false;

            for( unsigned i=3; i<=n/i; i+=2 )
                if( n%i == 0 )
                    return false;
            return true;
        };

        最大值 = maxval;
        for( unsigned i=0; i<=最大值; ++i )
            if( 是素数吗(i) )
                素数表.push_back( i );

        阶乘表.resize( 1+最大值, std::vector<unsigned>(素数表.size(),0) );
        for( unsigned i=2; i<=最大值; ++i )
        {
            阶乘表[i] = 阶乘表[i-1];

            unsigned t = i;
            for( size_t j=0; j!=素数表.size(); ++j )
            {
                if( t%素数表[j] == 0 )
                {
                    t /= 素数表[j];
                    ++阶乘表[i][j];
                    --j;
                }
            }
        }
    }

    unsigned 最大值;
    std::vector<unsigned> 素数表;
    std::vector<std::vector<unsigned>> 阶乘表;
};

const Fuck g_fuck( (100-3)*9/2 );

struct NumericByDecimal
{
    std::string data;

    NumericByDecimal()
    {
        data.push_back( 0 );
    }
    explicit NumericByDecimal( unsigned val )
    {
        data = std::to_string( val );
        std::reverse( data.begin(), data.end() );
        for( auto& c : data )
            c -= '0';
    }
    operator std::string() const
    {
        std::string result = data;
        std::reverse( result.begin(), result.end() );
        for( auto& c : result )
            c += '0';
        return result;
    }

    NumericByDecimal& operator+=( const NumericByDecimal& b )
    {
        data.resize( std::max(data.size(),b.data.size()) );
        unsigned carry = 0;
        for( size_t i=0; i!=data.size(); ++i )
        {
            carry += data[i] + (i<b.data.size() ? b.data[i] : 0);
            data[i] = carry%10;
            carry /= 10;
        }
        if( carry != 0 )
            data.push_back( carry );
        return *this;
    }

    NumericByDecimal& operator*=( unsigned b )
    {
        unsigned carry = 0;
        for( size_t i=0; i!=data.size(); ++i )
        {
            carry += data[i] * b;
            data[i] = carry%10;
            carry /= 10;
        }
        for( ; carry!=0; carry/=10 )
            data.push_back( carry%10 );
        return *this;
    }

    friend NumericByDecimal operator*( unsigned a, const NumericByDecimal& b )
    {
        NumericByDecimal result = b;
        result *= a;
        return result;
    }

    friend NumericByDecimal operator*( const NumericByDecimal& a, const NumericByDecimal& b )
    {
        NumericByDecimal result;
        for( size_t i=0; i!=b.data.size(); ++i )
        {
            NumericByDecimal t = b.data[i] * a;
            t.data.insert( 0, i, 0 );
            result += t;
        }
        return result;
    }
};

struct NumericByFactor
{
    std::vector<unsigned> data;

    operator NumericByDecimal() const
    {
        assert( data.size() == g_fuck.素数表.size() );

        NumericByDecimal result(1);

        std::vector<unsigned> temp = data;
        unsigned count0 = 0;
        if( g_fuck.素数表.size() >= 3 ) // 可能有2有5
        {
            count0 = std::min( temp[0], temp[2] );
            temp[0] -= count0;
            temp[2] -= count0;
        }
        for( size_t i=0; i!=g_fuck.素数表.size(); ++i )
        {
            if( temp[i] != 0 )
            {
                result *= g_fuck.素数表[i];
                --temp[i];
                --i;
            }
        }
        result.data.insert( 0, count0, 0 );
        return result;
    }
};

NumericByFactor C( unsigned n, unsigned k )
{
    NumericByFactor result;
    result.data.resize( g_fuck.素数表.size(), 0 );
    assert( n <= g_fuck.最大值 );
    if( n < k )
        return result;

    for( size_t i=0; i!=g_fuck.素数表.size(); ++i )
        result.data[i] = g_fuck.阶乘表[n][i] - g_fuck.阶乘表[k][i] - g_fuck.阶乘表[n-k][i];
    return result;
}

std::map< std::pair<unsigned,unsigned>, NumericByDecimal > g_buf;

// 将n分配给m个数，每个数在[0,9]区间内
NumericByDecimal bar10( unsigned n, unsigned m )
{
    if( n > 9*m )
        return NumericByDecimal(0);
    if( n > 9*m-n )
        n = 9*m-n;
    if( m == 0 )
        return NumericByDecimal(1);

    auto itor = g_buf.find( std::make_pair(n,m) );
    if( itor != g_buf.end() )
        return itor->second;

    if( n <= 9 )
    {
        // 在 n+m-1 中选 m-1 个的组合
        return C(n+m-1,m-1);
    }

    // 二分法
    NumericByDecimal result;
    for( unsigned i=0; i<=n && i<=m/2*9; ++i )
        result += bar10(i,m/2) * bar10(n-i,m-m/2);

    g_buf.insert( std::make_pair(std::make_pair(n,m),result) );
    return result;
}

//// 将n分配给m个数
//unsigned bar( unsigned n, unsigned m )
//{
//    if( n > 9*m )
//        return 0;
//    if( n > 9*m-n )
//        n = 9*m-n;
//    if( n == 0 )
//        return 1;
//    if( n == 1 )
//        return m;
//    if( m == 1 )
//        return 1;
//
//    unsigned result = 0;
//    for( unsigned k=0; k<=9 && k<=n; ++k )
//        result += bar(n-k,m-1);
//    return result;
//}

std::string foo( unsigned n )
{
    NumericByDecimal result( 9 + (n==1) );
    if( n > 2 )
    {
        for( unsigned a=1; a<=n-2 && a<=9; ++a )
            result += 10 * bar10(9*a,n-2);
    }
    if( n > 3 )
    {
        for( unsigned a=1; 11*a<=n-3; ++a )
            for( unsigned b=0; 11*a+b<=n-3; ++b )
                result += 10 * bar10(99*a+9*b,n-3);
    }
    return result;
}

int main( void )
{
     for( unsigned n=1; n<=100; ++n )
        printf( "f(%u) = %s\n", n, foo(n).c_str() );
}

#15

rjsp2022-04-05 01:35

按照题意模除 1000000007 的话，一秒内出结果

程序代码：

#include <stdio.h>
#include <map>

std::map< std::pair<unsigned,unsigned>, unsigned > g_buf;

// 将n分配给m个数，每个数在[0,9]区间内
unsigned bar10( unsigned n, unsigned m )
{
    if( n > 9*m )
        return 0;
    if( n > 9*m-n )
        n = 9*m-n;
    if( m==0 || m==1 )
        return 1;

    auto itor = g_buf.find( std::make_pair(n,m) );
    if( itor != g_buf.end() )
        return itor->second;

    // 二分法
    unsigned result = 0;
    for( unsigned i=0; i<=n && i<=m/2*9; ++i )
    {
        unsigned lhs = bar10(i,m/2);
        unsigned rhs = bar10(n-i,m-m/2);
        unsigned tmp = 1ull*lhs*rhs%1000000007;
        result = (result + tmp)%1000000007;
    }

    g_buf.insert( std::make_pair(std::make_pair(n,m),result) );
    return result;
}

unsigned foo( unsigned n )
{
    unsigned result = 9 + (n==1);

    unsigned result_tmp = 0;
    if( n > 2 )
    {
        for( unsigned a=1; a<=n-2 && a<=9; ++a )
            result_tmp = (result_tmp + bar10(9*a,n-2))%1000000007;
    }
    if( n > 3 )
    {
        for( unsigned a=1; 11*a<=n-3; ++a )
            for( unsigned b=0; 11*a+b<=n-3; ++b )
                result_tmp = (result_tmp + bar10(99*a+9*b,n-3))%1000000007;
    }

    result = (result_tmp*10ull+result)%1000000007;
    return result;
}

int main( void )
{
     for( unsigned n=1; n<=100; ++n )
        printf( "f(%u) = %u\n", n, foo(n) );
}

f(1) = 10
f(2) = 9
f(3) = 19
f(4) = 119
f(5) = 1119
f(6) = 11119
f(7) = 111119
f(8) = 1111119
f(9) = 11111119
f(10) = 111111119
f(11) = 111111112
f(12) = 111111032
f(13) = 110186552
f(14) = 772520689
f(15) = 860412280
f(16) = 800753384
f(17) = 535692814
f(18) = 845618240
f(19) = 577837544
f(20) = 266091166
f(21) = 984075764
f(22) = 108234084
f(23) = 35658741
f(24) = 892327708
f(25) = 31737456
f(26) = 494493925
f(27) = 593294515
f(28) = 274595905
f(29) = 948150459
f(30) = 690232915
f(31) = 46278984
f(32) = 462379795
f(33) = 334718682
f(34) = 401211904
f(35) = 95274004
f(36) = 741302008
f(37) = 699552277
f(38) = 502222505
f(39) = 987104115
f(40) = 594307537
f(41) = 553672869
f(42) = 193750702
f(43) = 946147597
f(44) = 83342656
f(45) = 180947735
f(46) = 554027738
f(47) = 912546596
f(48) = 742590540
f(49) = 244782734
f(50) = 679407534
f(51) = 551259762
f(52) = 136289125
f(53) = 881948450
f(54) = 989413317
f(55) = 376258951
f(56) = 667271306
f(57) = 897885929
f(58) = 863342957
f(59) = 644305035
f(60) = 83955394
f(61) = 618163190
f(62) = 651612064
f(63) = 928457537
f(64) = 676088244
f(65) = 334933268
f(66) = 58952455
f(67) = 614219334
f(68) = 83214562
f(69) = 931568487
f(70) = 426825899
f(71) = 62302377
f(72) = 532295247
f(73) = 481372539
f(74) = 115591038
f(75) = 327275846
f(76) = 563342199
f(77) = 467313888
f(78) = 374114616
f(79) = 725838252
f(80) = 308908880
f(81) = 970185973
f(82) = 297424720
f(83) = 356234391
f(84) = 917063290
f(85) = 217446576
f(86) = 97896987
f(87) = 7932157
f(88) = 80592245
f(89) = 36633282
f(90) = 826789496
f(91) = 547797280
f(92) = 413506696
f(93) = 685636682
f(94) = 924683961
f(95) = 58325784
f(96) = 358151799
f(97) = 393864665
f(98) = 303080475
f(99) = 714812370
f(100) = 260015775

#16

rjsp2022-04-05 23:13

回复 12楼逢考必过阿俊

图中的方法应该是极好的，是我当时想岔了。
等我有空，重新写一个

////// 2022-04-06 添加 //////

程序代码：

#include <stdio.h>

// 将n个棋子分配给m个格子，每个格子最多装9个棋子
unsigned bar10( unsigned n, unsigned m )
{
    // 最多是97个格子放进432个数
    static unsigned buf[98][433] = { 1 };

    if( n > 9*m )
        return 0;
    if( n > 9*m-n )
        n = 9*m-n;

    if( buf[m][n] != 0 )
        return buf[m][n];

    unsigned result = 0;
    for( unsigned i=0; i<=9 && i<=n; ++i )
        result = (result + bar10(n-i,m-1))%1000000007;

    buf[m][n] = result;
    return result;
}

unsigned foo( unsigned n )
{
    unsigned result = 1;

    if( n >= 3 ) // 9*a = c
    {
        for( unsigned a=1; a<=n-2 && a<=9; ++a )
            result = (result + bar10(9*a,n-2))%1000000007;
    }
    if( n >= 14 ) // 99*a + 9*b = d+e+f+g+h+i+j+k+l+m+n
    {
        for( unsigned a=1; 11*a<=n-3; ++a )
            for( unsigned b=0; 11*a+b<=n-3; ++b )
                result = (result + bar10(99*a+9*b,n-3))%1000000007;
    }

    result = ( result*10ull + (n!=1)*(1000000007-1) )%1000000007; // 仅当一位数时可以是全零，其它情况要减一
    return result;
}

int main( void )
{
     for( unsigned n=1; n<=100; ++n )
        printf( "f(%u) = %u\n", n, foo(n) );
}

[此贴子已经被作者于2022-4-6 22:07编辑过]

#17

jklqwe1112022-04-06 10:33

写了一个

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc,char* argv[])
{
    unsigned int foo( unsigned n ,unsigned int (* pf)[128]);
    unsigned int (* pf)[128]= (unsigned int( *)[128])malloc(sizeof(unsigned int )*9*101*128);
    memset((void*)pf,-1,sizeof(unsigned int )*9*101*128);
   for( unsigned int  n=1; n<=100; ++n ) printf( "f(%u) = %u\n", n, foo(n,pf) );
   free(pf);
   return 0 ;
}

int dfs10(int n,int m ,unsigned int (* pf)[128])

{

    if(( n > 9*m )||(n<0)) return 0;
    if( n > 9*m-n ) n = 9*m-n;
    if( m==0 || m==1 ||n==0) return 1;
    if(pf[n][m]!=0xffffffff) return  pf[n][m];
    unsigned int result = 0;
    for(int i=0 ;i<10;++i)
    {
        unsigned int res;
        if(n-i>=0 && pf[n-i][m-1]!=0xffffffff) res= pf[n-i][m-1] ;

        else
        {
            res=dfs10(n-i,m-1,pf)%1000000007;;
            if(n-i>=0) pf[n-i][m-1]=res ;
        }
        result=(result+res)%1000000007;
    }
    pf[n][m]=result;
    return result ;

}

unsigned int foo( unsigned int n,unsigned int (* pf)[128] )
{
    int dfs10(int n,int m ,unsigned int (* pf)[128]);
    unsigned int result = 9 + (n==1);
    unsigned int result_tmp = 0;
    if( n > 2 )
    {
        for( unsigned int a=1; a<=n-2 && a<=9; ++a )
            result_tmp = (result_tmp + dfs10(9*a,n-2,pf))%1000000007;
    }
    if( n > 3 )
    {
        for( unsigned int a=1; 11*a<=n-3; ++a )
            for( unsigned int b=0; 11*a+b<=n-3; ++b )
                result_tmp = (result_tmp + dfs10(99*a+9*b,n-3,pf))%1000000007;
    }

    result = (result_tmp*10ull+result)%1000000007;
    return result;
}