求满足约束的有效数组总数：优化解法及算法思路咨询

问题分析 #

我们需要统计所有满足以下条件的正整数数组数目：

1. 数组元素之和恰好为N；
2. 任意相邻元素满足 K*A[i] >= A[i+1]。
   结果对 10^9+7 取模。

回溯法会因N较大时（如N>1000）时间复杂度爆炸，因此需采用动态规划结合前缀和优化的方法解决。

动态规划思路 #

状态定义 #

定义三个核心数组：

• dp[n]：和为n的有效数组总数；
• cnt[n][x]：和为n且最后一个元素为x的有效数组数目；
• sum_dp[n][t]：和为n且最后一个元素大于等于t的有效数组数目（前缀和数组，用于快速查询）。

边界条件 #

• 对于所有1<=x<=n，当n=x时，cnt[n][x] = 1（对应单独元素数组[x]）；
• dp[n]初始值为1（对应单独元素数组[n]）；
• sum_dp[n][n+1] = 0，sum_dp[n][1] = dp[n]。

转移方程 #

1. 计算cnt[n][x]：
   当n > x时，要构造和为n且最后一个元素为x的数组，需在和为n-x的有效数组后添加x，且原数组最后一个元素y满足K*y >= x（即y >= ceil(x/K)）。用整数除法计算ceil(x/K)为(x + K - 1) // K，因此：

   cnt[n][x] = sum_dp[n-x][(x + K - 1) // K] if (x + K - 1) // K <= n-x else 0
   

2. 更新dp[n]：
   dp[n]是所有cnt[n][x]的和（x从1到n），即单独元素情况加上所有长度≥2的数组情况：

   dp[n] = (dp[n] + sum_{x=1}^{n-1} cnt[n][x]) % MOD
   

3. 维护sum_dp[n]：
   从后往前计算前缀和，保证查询效率：

   sum_dp[n][t] = (sum_dp[n][t+1] + cnt[n][t]) % MOD
   

空间优化 #

上述O(N²)空间复杂度的方法在N较大时内存占用过高，可做如下优化：

• 利用滚动数组：计算cnt[n][x]仅需用到sum_dp[m]（m = n-x <n），因此可复用数组存储历史sum_dp数据；
• 用一维数组维护sum_dp的逆序前缀和，避免二维数组的空间浪费。

高阶优化：O(N log N) 解法 #

当N达到1e5级别时，O(N²)方法仍不可行。可通过分组求和优化：
观察ceil(x/K)的取值范围为1到ceil(n/K)，将x按ceil(x/K)的取值分组（每组x对应[(t-1)*K +1, t*K]），对每组内的sum_dp[n-x][t]求和后累加，将时间复杂度降至O(N log N)。

代码框架（O(N²) 版本） #

MOD = 10**9 + 7

def count_valid_arrays(N, K):
    dp = [0] * (N + 1)
    cnt = [[0] * (N + 2) for _ in range(N + 1)]
    sum_dp = [[0] * (N + 2) for _ in range(N + 1)]
    
    for n in range(1, N + 1):
        # 单独元素数组的情况
        cnt[n][n] = 1
        dp[n] = 1
        
        # 计算所有长度≥2的数组情况
        for x in range(1, n):
            m = n - x
            t = (x + K - 1) // K
            if t > m:
                cnt[n][x] = 0
            else:
                cnt[n][x] = sum_dp[m][t]
            dp[n] = (dp[n] + cnt[n][x]) % MOD
        
        # 更新前缀和数组
        sum_dp[n][n + 1] = 0
        for t in range(n, 0, -1):
            sum_dp[n][t] = (sum_dp[n][t + 1] + cnt[n][t]) % MOD
    
    return dp[N]

注意事项 #

• 所有运算需对10^9+7取模，避免数值溢出；
• 题目中K为正整数（示例K=3），若K=0需单独处理；
• 数组元素均为正整数，因此所有中间变量x、m需≥1。

内容的提问来源于stack exchange，提问作者Ashutosh A M