user

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
乘积之和
n的一个分拆是指一组无序且和为n的正整数。
例如，5的分拆包括：
{5}、{1,4}、{2,3}、{1,1,3}、{1,2,2}、{1,1,1,2}和{1,1,1,1,1}。

进一步定义函数D(p)如下：
D(1)=1
对于任意质数p,D(p)=1
对于任意正整数p,q>1有D(pq)=D(p)q+D(q)p
 

考虑n的分拆a_1,a_2,...,a_k。
这一分拆的得分是：
P=\prod_{j=1}^{k}D(a_j)

记G(n)为n的所有分拆的得分P之和。
可以验证G(10)=164。

再定义：S(N)=\sum_{n=1}^{N}G(n)
已知S(10)=396。
求S(5\times 10^4) \mod 999676999。

我的思路:首先这个分拆是无序的,{1,2}和{2,1}不做区分,所以我们限制一下转移最大限制:单步长度不超过当前数字,例如2可以转移到3 4不可以转移到5,3可以转移到4 5 6不可以转移到7.  
然后用筛法把D函数算出来之后直接dp转移即可.
请给我cpp代码.

deepseek v4 flash

根据你的需求，这是一个计算 S(5×10^4) mod 999676999 的 C++ 代码。我按照你描述的思路实现：

  1. 筛法预计算 D 函数：利用质数筛和递推关系计算所有 D 值
  2. DP 计算分拆得分：限制转移时数字非递减（无序分拆）
  3. 累加得到结果：计算所有 G(n) 并求和得到 S(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

const int N = 50000;
const long long MOD = 999676999;

// 预计算 D 函数和质数标记
vector<long long> D(N + 1);
vector<bool> is_prime(N + 1, true);

void precompute_D() {
    // 质数筛
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= N; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    // 初始化 D 函数
    D[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            D[i] = 1;
        }
    }
    
    // 对于合数，找到任意一个质因子分解
    // D(pq) = D(p)*q + D(q)*p
    for (int i = 2; i <= N; i++) {
        if (!is_prime[i] && D[i] == 0) {
            // 找最小质因子
            for (int p = 2; p * p <= i; p++) {
                if (is_prime[p] && i % p == 0) {
                    int q = i / p;
                    // 递归确保 D[p] 和 D[q] 已计算
                    D[i] = (D[p] * q + D[q] * p) % MOD;
                    break;
                }
            }
        }
    }
}

// 计算 G(n) 和 S(N)
pair<vector<long long>, long long> compute_G_and_S() {
    // dp[i] 表示数字 i 的所有分拆的得分之和 = G(i)
    vector<long long> dp(N + 1, 0);
    dp[0] = 1; // 空分拆得分为 1（乘法单位元）
    
    // 枚举可用数字（从小到大，保证非递减）
    for (int num = 1; num <= N; num++) {
        long long D_val = D[num];
        // 完全背包：正序更新，允许重复使用同一个数字
        for (int sum = num; sum <= N; sum++) {
            // 用一次 num：剩余 sum-num 的每个分拆乘上 D(num)
            dp[sum] = (dp[sum] + dp[sum - num] * D_val) % MOD;
        }
    }
    
    // G(n) = dp[n]，但要去掉空分拆的影响
    // 实际上 dp[n] 已经是 G(n)，因为 dp[0]=1 贡献了空分拆作为乘法单位
    
    // 计算 S(N) = sum(G(1)..G(N))
    long long S = 0;
    for (int n = 1; n <= N; n++) {
        S = (S + dp[n]) % MOD;
    }
    
    return {dp, S};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cout << "预计算 D 函数..." << endl;
    precompute_D();
    
    // 验证 D 函数的小值
    cout << "D 函数验证：" << endl;
    cout << "D(1) = " << D[1] << " (应为 1)" << endl;
    cout << "D(2) = " << D[2] << " (应为 1, 质数)" << endl;
    cout << "D(4) = " << D[4] << " (D(2)*2 + D(2)*2 = 1*2+1*2=4)" << endl;
    cout << "D(6) = " << D[6] << " (D(2)*3 + D(3)*2 = 1*3+1*2=5)" << endl;
    
    cout << "\n计算 G(n) 和 S(N)..." << endl;
    auto [G, S] = compute_G_and_S();
    
    // 验证小值
    cout << "\n小值验证：" << endl;
    for (int n = 1; n <= 10; n++) {
        cout << "G(" << n << ") = " << G[n] << endl;
    }
    
    // 验证 G(10) = 164
    cout << "\nG(10) = " << G[10] << " (应为 164)" << endl;
    
    // 验证 S(10) = 396
    long long S10 = 0;
    for (int n = 1; n <= 10; n++) {
        S10 = (S10 + G[n]) % MOD;
    }
    cout << "S(10) = " << S10 << " (应为 396)" << endl;
    
    // 最终结果
    cout << "\n最终结果：" << endl;
    cout << "S(50000) mod 999676999 = " << S << endl;
    
    // 额外信息
    cout << "\n统计信息：" << endl;
    cout << "G(100) = " << G[100] << endl;
    cout << "G(1000) = " << G[1000] << endl;
    cout << "G(5000) = " << G[5000] << endl;
    cout << "G(50000) = " << G[50000] << endl;
    
    return 0;
}

这个代码的核心要点：

  1. D 函数计算：

    • 先用筛法找出所有质数，D(p) = 1
    • 对合数 n = p × q（p 是质因子），递推：D(n) = D(p)×q + D(q)×p

  2. DP 转移：

    • dp[sum] = 所有分拆的得分之和（即 G(sum)）
    • 外层从小到大枚举数字 num，保证非递减顺序
    • 内层完全背包正序更新：dp[sum] += dp[sum - num] × D(num)
    • 这等价于：所有和为 sum-num 的分拆，加上 num 后得分乘 D(num)

  3. 复杂度：

    • D 函数预计算：O(N log log N)
    • DP 计算：O(N²) ≈ 1.25×10^9，在现代 C++ 中可接受（约 10-30 秒）
    • 空间：O(N)

运行后会输出 S(50000) mod 999676999 的值。这个算法完全符合你描述的无序分拆限制。

fun fact

一发过了.