题意分析

给定一个整数序列和一个整数K，需要判断是否可以在序列中的整数之间添加+或-运算符，使得最终的表达式值能被K整除。例如，序列17, 5, -21, 15可以通过添加运算符得到-14（17+5-21-15），能被7整除，因此该序列对7是可分的。

关键条件：

• 序列长度N范围：1 ≤ N ≤ 10000
• 除数K范围：2 ≤ K ≤ 100
• 序列中每个整数的绝对值不超过10000
• 结果只需判断是否存在一种运算符组合使得表达式值能被K整除

解题思路

这是一个典型的动态规划问题，可以通过维护余数状态来解决。基本思路是：

1. 状态定义：使用一个二维数组或滚动数组来记录前i个整数能得到的所有余数状态。由于K的范围较小（≤100），可以高效地维护这些状态。

2. 状态转移：对于每个新的整数，考虑将其加入之前的所有可能状态，并计算新的余数。具体来说，对于每个已有的余数r，加上或减去当前整数后，计算新的余数。

3. 模运算优化：利用模运算的性质，将所有余数转换到[0, K-1]的范围内，避免负数和溢出问题。

具体步骤：

1. 初始化：从第一个整数开始，初始化其对应的余数状态。
2. 动态规划：遍历每个后续整数，对于每个已有的余数状态，计算加上或减去当前整数后的新余数，并更新状态数组。
3. 结果判断：检查最终状态数组中是否存在余数0。

标准程序

下面是解决这个问题的标准程序：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_K = 100;

int main() {
    int n, k;
    while (cin >> n >> k) {
        bool dp[2][MAX_K] = {false};  // 使用滚动数组优化空间
        
        int first;
        cin >> first;
        // 处理第一个数的余数
        int mod = ((first % k) + k) % k;  // 确保余数为非负数
        dp[0][mod] = true;
        
        int current = 0;
        for (int i = 1; i < n; i++) {
            int num;
            cin >> num;
            current ^= 1;  // 切换当前数组和前一个数组
            memset(dp[current], false, sizeof(dp[current]));
            
            for (int r = 0; r < k; r++) {
                if (dp[current ^ 1][r]) {  // 如果前一个状态存在
                    // 计算加上当前数后的余数
                    int add_mod = (r + num) % k;
                    add_mod = (add_mod + k) % k;  // 确保非负
                    dp[current][add_mod] = true;
                    
                    // 计算减去当前数后的余数
                    int sub_mod = (r - num) % k;
                    sub_mod = (sub_mod + k) % k;  // 确保非负
                    dp[current][sub_mod] = true;
                }
            }
        }
        
        if (dp[current][0]) {
            cout << "Divisible" << endl;
        } else {
            cout << "Not divisible" << endl;
        }
    }
    return 0;
}

代码解释

动态规划数组：

• 使用二维数组dp[2][MAX_K]作为滚动数组，dp[current][r]表示前i个整数能否得到余数r
• 通过异或操作current ^= 1在两个数组之间切换，优化空间使用

状态转移：

• 对于每个新的整数，遍历所有可能的余数状态
• 计算加上或减去当前整数后的新余数，并更新状态数组
• 使用模运算和额外的加法确保余数在[0, K-1]范围内

结果判断：

• 检查最终状态数组中是否存在余数0，存在则输出"Divisible"，否则输出"Not divisible"