UVa 10616 - Divisible Group Sums

称号：给你n数字。免去m一个，这使得他们可分割d。问：有多少种借贷。

分析：dp，D01背包。

背包整数分区。

首先。整点d。则全部数字均在整数区间[0，d)上；

然后，确定背包容量，最大为20*10 = 200，计算二维01背包；

最后，求出全部能整除d的整数取法的和就可以。

说明：注意使用long long防止溢出；注意数据中的负数。

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

long long f[222][11];

int data[222],r[222];

int main()

{

	int N,Q,M,D,T = 1;

	while (~scanf("%d%d",&N,&Q) && Q+N) {

		for (int i = 0 ; i < N ; ++ i)

			scanf("%d",&data[i]);

		printf("SET %d:\n",T ++);

		for (int q = 0 ; q < Q ; ++ q) {

			scanf("%d%d",&D,&M);

			for (int i = 0 ; i < N ; ++ i) {

				r[i] = data[i]%D;

				if (r[i] < 0) r[i] += D;

			}

			for (int i = 0 ; i < 222 ; ++ i)

			for (int j = 0 ; j < 11 ; ++ j)

				f[i][j] = 0LL;

			f[0][0] = 1LL;

			for (int i = 0 ; i < N ; ++ i)

			for (int j = M ; j > 0 ; -- j)

			for (int k = 200 ; k >= r[i] ; -- k)

				f[k][j] += f[k-r[i]][j-1];

			long long count = 0LL;

			for (int i = 0 ; i <= 200 ; i += D)

				count += f[i][M];

			printf("QUERY %d: %lld\n",q+1,count);

		}

	}

    return 0;

}