今日是2010年9月17日，距我开这个博客已有近一年的时间了，这一年里因为毕业找工作出现的一些繁琐之事，已有将近8、9个月没有学习程序了。这一个月来才又开始拿起编程的书学习，说来我也很惭愧。今天又看了第四次的编程比赛题，我以前想到的那种算法（用栈，把加减号用二进制的0和1表示）现在竟想不起来了，不过重看了一下后很快就理解了。不过nopeak的算法我看了好一会儿才懂，他的算法的确很妙，只用了两个大小为100的数组（因为K最大为100，可输入的最大的数是10000，10000除以100最大的余数是99，所以数组的大小设定为100即可），而每输入一次数都和上一次的余数相加再除以K求余，这样可以减少因为相加之后总数太大而导致的溢出。
下面我把他的代码写下来并附上注释：
#include <iostream.h>
#define MAX1 100
#define MAX2 10000
int main()
{
int a[MAX1]={0},n,k;
while(cin >> n >> k)
{
int temp;
cin >> temp;
a[(temp+MAX2*k)%k]=1; // 这行代码是求出输入的temp除以k之后的余数，并用这个余数作为数组下标
while(--n)
{
int b[MAX1]={0}; //每次进入这个while循环都要重新置数组b的元素全为0
cin >> temp;
for(int i=0;i<k;i++) //新输入的数与上轮存在的余数进行加和减运算
{
if(a[i]) //这个for循环找到数组a中值为1的元素的下标，此下标即上一次输入的数除以k之后的余数
{
b[(i+temp+MAX2*k)%k]=1; //上一次的余数i加上新输入的temp之和和除以k的余数作为新的下标
b[(i-temp+MAX2*k)%k]=1;
}
}
for(i=0;i<k;i++)a[i]=b[i];//某一轮输入结束后,所有存在的余数对应的a数组值取1,别的置0
}
if(a[0]) //a[0]中的0说明余数就是0，即所求的总和可以被k整除
cout << "Divisible" << endl;//最后一轮输入结束后,看是否有余数为0,即能整除的结果
else cout << "Not divisible" << endl;
}
return 0;
}
每输入的一个数都与上一次数组a中的余数（用下标表示的）相加或相减，这样第一次输入一个数时数组a中只有一个余数，第二次输入一个数时要与上一次数组a中的余数（用下标表示的）相加或相减，这样第二次输入数后数组a中有两个余数，这样依次类推，第三次输入一个数时数组a中有四个余数，第四次时是八个，等等。但从第二次输入开始，计算出的余数可能会和之前的余数重复，不过这并不影响，因为重复的情况只用计算一次就可以了，这也正是第一次for循环中i只用小于k的原因。第二个while循环（即while（--n））结束之后只用判断a[0]是不是为1即可，只要有一次（可能会重复置它为1）为1即可。 （就像几个很大的数的和除以一个不是很大的数m，其实不用将它们真的相加之后再除以m，只用计算每个数除以m的余数，然后再将余数相加再除以m即可计算出结果）
nopeak 的分析是这样的:
对有模运算出现的问题，一般都会用到下面的公式
(a + b) mod c = (a mod c + b mod c) mod c
对那些绝对值10000内的数字来说，其实他们的有效值仅仅就是[0..k-1]，而他们的和差如果超过了这个范围，也只要取模映射到这个范围内即可。
如果直接用穷举法，需要计算所有组合，复杂度为O(2^n)。这对于N到达10000的题目来说，显然不可行。如果利用上面的公式，可以知道，任意个数字的和差都能映射到[0..k-1]范围内，它们的和差组合有2^(n-1)种情况。根据抽屉原理，必然存在许多组合，它们的结果相同。对相同的结果，在这任意个数字上再添加一个（或一些）数字得到的一组结果也是一样的。所以对穷举来说这里存在重复计算。为了去掉这些重复计算，可以把得到同样结果的情况归到一起：
对前i个数字，如果它们的各种组合能够得到的结果为集合Ai
那么对前i+1个数字，它们的结果为集合Ai+1{a,b|a = (t + d) mod k, b = (t - d) mod k, t属于Ai, d为第i+1个数字}
集合A1就只包含第一个数字。
这就是一个动态规划的程序了。复杂度为O(N * k)，估计一下时间10000*100 = 10^6。根据目前的cpu处理能力，一般10^8个基本运算的时间消耗达到秒的量级。所以这个程序需要的时间大约为0.01秒的数量级。
计算时，用一个数组表示集合A, 由于k最大为100，这个集合只需要100个元素即可。数组A[i]为0表示i不是A的元素，否则表示是A的元素。每次只需要将集合A中每个元素加上或者减去新元素（并映射到[0..k-1]）就得到新集合的元素。