程序代码：

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

程序代码：

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

程序代码：

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

程序代码：

#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编辑过]

程序代码：

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