これは条件付きの正整数分割問題であり、直接的な計算式は存在しません。

小規模な場合は全探索が可能です。数百桁規模になると動的計画法が有効です。しかし数千桁規模では動的計画法でも数十分から数時間要します。さらに万桁規模になると、時間・空間的な制約によりPCでの計算は不可能になります。

「挿入法と包含排除原理の組み合わせ」が強力な手法です。

核心となるアルゴリズムは以下の式に基づいています：

先頭が0になる場合を除く必要があります：
total = Σ(i = 0～n) - Σ(i = 0～n-1)

Pythonには組み込みの多倍長整数と組み合わせ計算関数があり、テストした結果、Fortranを上回る効率を示しました。

Pythonコード例：

# 1000桁の正整数で、各位の数字の和が5000となる個数を計算
# mathematical_combinatorics.py
# 2024-07-14

from math import comb
import sys
import time

def calculate_combinations(length, digit_sum, base):
    """
    包含排除原理を用いて組み合わせ数を計算
    
    引数:
    length -- 正整数の桁数
    digit_sum -- 各桁の数字の合計
    base -- 各桁の取りうる最大値（この場合は10進数なので10）
    
    戻り値:
    条件を満たす組み合わせ数
    """
    result = 0
    for k in range(length + 1):
        if k * base > digit_sum:
            break
        sign = (-1) ** k
        term = sign * comb(length - 1 + digit_sum - k * base, length - 1) * comb(length, k)
        result += term
    return result

def count_valid_numbers(num_digits, target_sum):
    """
    指定された条件を満たす正整数の個数を計算
    
    引数:
    num_digits -- 正整数の桁数
    target_sum -- 目標とする各位の数字の合計
    
    戻り値:
    条件を満たすn桁正整数の個数
    """
    total_combinations = calculate_combinations(num_digits, target_sum, 10)
    invalid_combinations = calculate_combinations(num_digits - 1, target_sum, 10)
    return total_combinations - invalid_combinations

# メイン処理
if __name__ == "__main__":
    digit_count = 1000
    sum_target = 5000
    
    begin = time.perf_counter()
    answer = count_valid_numbers(digit_count, sum_target)
    finish = time.perf_counter()
    
    execution_time = (finish - begin) * 1000
    
    print(f"計算結果: {answer}")
    print(f"実行時間: {execution_time:.0f} ミリ秒")

桁数1000、数字の和5000の場合の実行時間は507ミリ秒でした。

計算結果：

計算結果: 10285365067195108279225142980141878600436775717079668098763107749084681963865663398549438382871357086343262593006829915422766021250213523036365720794008181853252571208894977792325007703100745052309162270431546632904405801249072129315390740993369189182722741184529959028657805877226409256723754071554845143402710377458469861704855510858930204077579300369143561806187085658687038624639772365001271352767972620393008430988939906039570647457525714932032736164841522324617879072246419422236156405366464153445733145564034044182972376371702400606659207050480816922601281434846851694581686209528756902423796651122212073205284566821880292636599595714274027420413877993217075979458903453123944101597589100389223674589656462816635288040086976653861613595937991672823392045555064175060116269398996825041632535493492592636186432758707578488603262994149040157870336864388850537821127957936706260836057978829775191634098139364843182377363956436912804227224405620901587681832910238503135057103703350309161710
実行時間: 507 ミリ秒

補足：オンラインコンパイラでの実行結果のスクリーンショット