2013年9月1日

UVa 10616 - Divisible Group Sums

#include <cstdio>

int main() {
  int N, Q, S = 1;
  while (scanf("%d%d", &N, &Q) && N) {
    printf("SET %d:\n", S++);
    int num[200];
    for (int i = 0; i < N; i++) {
      scanf("%d", &num[i]);
    }
    int q = 1;
    while (Q--) {
      int D, M;
      scanf("%d%d", &D, &M);
      long long dp[11][20] = {1};
      for (int i = 0; i < N; i++) {
        for (int m = M; m; m--) {
          for (int r = 0; r < D; r++) {
            dp[m][r] += dp[m - 1][(r - num[i] % D + D) % D];
          }
        }
      }
      printf("QUERY %d: %lld\n", q++, dp[M][0]);
    }
  }
  return 0;
}

沒有留言:

張貼留言