fork download
copy 
  1. #include <cstring>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <memory.h>
  21. #include <cassert>
  22.  
  23. using namespace std;
  24.  
  25. const int md = 1000000007;
  26.  
  27. inline void add(int &a, int b) {
  28.   a += b;
  29.   if (a >= md) a -= md;
  30. }
  31.  
  32. inline int mul(int a, int b) {
  33.   return (long long)a * b % md;
  34. }
  35.  
  36. const int MAX = 1111111;
  37.  
  38. int fact[MAX], inv[MAX];
  39.  
  40. int C(int n, int k) {
  41.   if (n < 0 || k < 0 || k > n) return 0;
  42.   return mul(fact[n], mul(inv[k], inv[n - k]));
  43. }
  44.  
  45. int f[2010][2], nf[2010][2];
  46.  
  47. int cnt[2010];
  48. int ways[2010];
  49. int ans[2010];
  50.  
  51. int main() {
  52.   fact[0] = inv[0] = 1;
  53.   for (int i = 1; i < MAX; i++) {
  54.     fact[i] = (long long)fact[i - 1] * i % md;
  55.     int x = 1, step = 1 << 30;
  56.     while (step > 0) {
  57.       x = (long long)x * x % md;
  58.       if (step & (md - 2)) x = (long long)x * fact[i] % md;
  59.       step >>= 1;
  60.     }
  61.     inv[i] = x;
  62.   }
  63.   int n;
  64.   scanf("%d", &n);
  65.   for (int i = 1; i <= 1000; i++) cnt[i] = 0;
  66.   for (int i = 0; i < n; i++) {
  67.     int foo;
  68.     scanf("%d", &foo);
  69.     cnt[foo]++;
  70.   }
  71.   for (int i = 0; i <= 2000; i++) f[i][0] = f[i][1] = 0;
  72.   f[0][0] = 1;
  73.   for (int t = 1; t <= 1000; t++) {
  74.     int addv = t + 1;
  75.     for (int u = 0; u <= 2000 / addv; u++) {
  76.       ways[u] = C(cnt[t], u);
  77.     }
  78.     for (int i = 0; i <= 2000; i++) nf[i][0] = nf[i][1] = 0;
  79.     for (int i = 0; i <= 2000; i++)
  80.       for (int p = 0; p <= 1; p++)
  81.         for (int it = 0, j = i; j <= 2000; it++, j += addv) {
  82.           add(nf[j][(p + it) & 1], mul(f[i][p], ways[it]));
  83.         }
  84.     for (int i = 0; i <= 2000; i++) {
  85.       f[i][0] = nf[i][0];
  86.       f[i][1] = nf[i][1];
  87.     }
  88.   }
  89.   for (int sw = 0; sw <= 2000; sw++) {
  90.     int res = 0;
  91.     for (int over = 0; over <= sw; over++)
  92.       for (int p = 0; p <= 1; p++) {
  93.         int ft = mul(f[over][p], C(sw - over + n - 1, n - 1));
  94.         if (p == 1) ft = md - ft;
  95.         add(res, ft);
  96.       }
  97.     ans[sw] = res;
  98.   }
  99.   int tt;
  100.   scanf("%d", &tt);
  101.   while (tt--) {
  102.     int foo;
  103.     scanf("%d", &foo);
  104.     printf("%d\n", ans[foo]);
  105.   }
  106.   return 0;
  107. }
  108.  
Runtime error #stdin #stdout 2.63s 12032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lxegA2
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!