CodeChef--Cards, bags and coins

제목 링크
Yet another game from chef. Chef gives you N cards and M bags. Each of the N cards has an integer written on it. Now chef asks you to close your eyes and choose a subset of them. He then sums the numbers written on chosen cards, takes its absolute value and gives you those many coins. You win the game if you can divide these coins into M bags with each bag having equal share. As a first step to calculate the probability of winning, you would like to know the number of different subsets which will make you win. Note that all the cards are of different color, so even if 2 cards have the same number written on it, they are still considered as different cards.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.First line of each test case contains two integers N and Q. Q denotes the number of queries to be answered. Second line of each test case contains N integers, the numbers written on cards.Following Q lines contain an integer M.
Output
For each query output the required Answer modulo 1000000009. Answer is the number of subsets that will ensure you win.
Constraints

1 ≤ T ≤ 3

1 ≤ N ≤ 100000

1 ≤ Q ≤ 30

1 ≤ M ≤ 100

-10^9 ≤ Number on card ≤ 10^9

Example

Input

2

5 1

1 2 -1 4 5

9

5 2

1 2 3 4 5

5

15



Output

4

8

2

Explanation
Test Case #1, Query #1{}, {1,-1}, {1,-1,4,5}, {4,5} are winning subsets. Sums are 0, 0, 9, 9 respectively.
Test Case #2, Query #1{}, {5}, {1,4}, {2,3}, {1,4,5}, {2,3,5}, {1,2,3,4}, {1,2,3,4,5} are winning subsets. Sums are 0, 5, 5, 5, 10, 10, 10, 15 respectively.
Test Case #2, Query #2{}, {1,2,3,4,5} are winning subsets. Sums are 0 and 15 respectively.
Author's Note
Time Limit is not very strict (Yes, not very loose either) if correct Algorithm is used.Author's solution passes with 2 sec Time Limit (C++ solution, using scanf and printf).Maximum Input File Size < 4MB.
제목: n개의 수를 제시하고 그 다음에 또 하나의 숫자 m가 있다. n개의 수 중에서 몇 개의 수를 골라서 이 수의 합이 m의 배수가 될 수 있는지 묻는다.
좋은 문제예요. 많이 배웠어요.먼저 자신의 기초적인 차이에 대해 땀을 흘렸다.
첫째, C(n,k)에 대한 타계...여기서 자신의 생각을 말해 봅시다. 만약에 n<10^3이라면 이 데이터량은 기본적으로 점차적으로 추정할 수 있습니다. 2차원수조 C[n][k]로 기록할 수 있습니다.
이 문제의 n<10^5는 분명히 큰 시계를 열 수 없기 때문에 C(n,k)=n!/(k! * (n -k)!)..이렇게 하면 n을 기록할 수 있어요!n!역으로 해답을 구하고,
만약에 제목이 제시한 모델이 질수라면 페마소정리를 통해 한 수의 역원을 쉽게 구할 수 있다. 물론 gcd를 확장해도 된다.
그 다음으로 이 문제의 사고방식에 대해 제목과 데이터 범위를 보면 실제 실제 데이터 범위는 [0,m)밖에 없다고 생각해야 한다. 그래서 매번 질문을 할 때마다 A[i]모드m를 직접 하고
숫자마다 나오는 횟수를 얻다.이렇게 하면 dp의 기본 모델을 얻을 수 있다.
dp[i][j]는 0에서 i까지의 숫자 중 일부 모델 m을 j로 선택한 방안의 수를 나타낸다. 그리고 dp[i][j]는 dp[i-1][0.m-1]에서 얻을 수 있다.
 Accepted Code:

 1 /*************************************************************************

 2     > File Name: ANUCBC.cpp

 3     > Author: Stomach_ache

 4     > Mail: [email protected]

 5     > Created Time: 2014 09 04      14 13 00 

 6     > Propose: 

 7  ************************************************************************/

 8 #include <cmath>

 9 #include <string>

10 #include <cstdio>

11 #include <fstream>

12 #include <cstring>

13 #include <iostream>

14 #include <algorithm>

15 using namespace std;

16 /*Let's fight!!!*/

17 

18 #define rep(i, n) for (int i = (0); i < (n); i++)

19 #define FOR(i, a, b) for (int i = (a); i <= (b); i++)

20 const int MAX_N = 100050;

21 const int MAX_M = 101;

22 const int MOD = 1e9 + 9;

23 typedef long long LL;

24 LL fact[MAX_N], ifact[MAX_N];

25 

26 LL pow_mod(LL a, LL b) {

27       LL res = 1;

28     while (b) {

29           if (b & 1) res = (res * a) % MOD;

30         a = (a * a) % MOD;

31         b >>= 1;

32     }

33     return res;

34 }

35 

36 //fact and ifact

37 void init() {

38       fact[0] = fact[1] = ifact[0] = ifact[1] = 1;

39     FOR (i, 2, MAX_N - 50) {

40           fact[i] = (fact[i - 1] * i) % MOD;

41         ifact[i] = (ifact[i - 1] * pow_mod(i, MOD - 2)) % MOD;

42     }

43 }

44 

45 int C(int n, int k) {

46       return (fact[n] * ifact[k] % MOD) * ifact[n - k] % MOD;

47 }

48 

49 int A[MAX_N], cnt[MAX_M];

50 LL dp[MAX_M][MAX_M], choose[MAX_M][MAX_M];

51 

52 int main(void) {

53     init(); // precomputation 

54 

55     ios::sync_with_stdio(false);

56     int T;

57     cin >> T;

58     while (T--) {

59         int N, Q, M;

60         cin >> N >> Q;

61         rep (i, N) cin >> A[i];

62         while (Q--) {

63             cin >> M;

64             memset(cnt, 0, sizeof(cnt));

65             rep (i, N) cnt[(A[i] % M + M) % M]++;

66 

67             memset(choose, 0, sizeof(choose));

68             rep (i, M) FOR (j, 0, cnt[i]) {

69                   choose[i][j * i % M] = (choose[i][j * i % M] + C(cnt[i], j)) % MOD;

70             }

71 

72             memset(dp, 0, sizeof(dp));

73             dp[0][0] = choose[0][0];

74             FOR (i, 1, M-1) rep (j, M) rep (k, M) dp[i][j] = (dp[i][j] + dp[i - 1][(j - k + M) % M] * choose[i][k]) % MOD;

75 

76             cout << dp[M - 1][0] << endl;

77         }

78     }

79     return 0;

80 }