Advertisement
Guest User

Untitled

a guest
Sep 19th, 2016
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.16 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. const int MOD = (int)1e9 + 7;
  10. int add(int x, int y)
  11.     {
  12.     x += y;
  13.     if (x >= MOD) return x - MOD;
  14.     return x;
  15. }
  16. int sub(int x, int y)
  17.     {
  18.     x -= y;
  19.     if (x < 0) return x + MOD;
  20.     return x;
  21. }
  22. int mult(int x, int y)
  23.     {
  24.     return ((ll)x * y) % MOD;
  25. }
  26.  
  27. const int LOG = 19;
  28. const int N = (1 << LOG) + 5;
  29. int a[N];
  30. int b[N << 1];
  31. int c[N << 1];
  32. const int L = 16;
  33.  
  34. void printPoly(int* A, int len)
  35.     {
  36.     printf("{ ");
  37.     for (int i = 0; i < len; i++)
  38.         printf("%d ", A[i]);
  39.     printf("}");
  40. }
  41.  
  42. void multPoly(int s1, int s2, int len)
  43.     {
  44.     /*
  45.     printPoly(b + s1, len);
  46.     printf(" * ");
  47.     printPoly(b + s2, len);
  48.     printf("\n");
  49.     */
  50.     for (int i = s1; i < s1 + (len << 1); i++)
  51.         c[i] = 0;
  52.     if (len <= L)
  53.         {
  54.         for (int i = 0; i < len; i++)
  55.             for (int j = 0; j < len; j++)
  56.                 {
  57.                 c[s1 + i + j] = add(c[s1 + i + j], mult(b[s1 + i], b[s2 + j]));
  58.             }
  59.         return;
  60.     }
  61.     int len2 = len >> 1;
  62.     int s3 = s2 + len;
  63.     int s4 = s3 + len2;
  64.    
  65.     for (int i = 0; i < len2; i++)
  66.         {
  67.         b[s3 + i] = b[s1 + i];
  68.         b[s4 + i] = b[s2 + i];
  69.     }
  70.     multPoly(s3, s4, len2);
  71.     for (int i = 0; i < len; i++)
  72.         {
  73.         c[s1 + i] = add(c[s1 + i], c[s3 + i]);
  74.         c[s1 + len2 + i] = sub(c[s1 + len2 + i], c[s3 + i]);
  75.     }
  76.    
  77.     for (int i = 0; i < len2; i++)
  78.         {
  79.         b[s3 + i] = b[s1 + len2 + i];
  80.         b[s4 + i] = b[s2 + len2 + i];
  81.     }
  82.     multPoly(s3, s4, len2);
  83.     for (int i = 0; i < len; i++)
  84.         {
  85.         c[s1 + len + i] = add(c[s1 + len + i], c[s3 + i]);
  86.         c[s1 + len2 + i] = sub(c[s1 + len2 + i], c[s3 + i]);
  87.     }
  88.    
  89.     for (int i = 0; i < len2; i++)
  90.         {
  91.         b[s3 + i] = add(b[s1 + i], b[s1 + len2 + i]);
  92.         b[s4 + i] = add(b[s2 + i], b[s2 + len2 + i]);
  93.     }
  94.     multPoly(s3, s4, len2);
  95.     for (int i = 0; i < len; i++)
  96.         {
  97.         c[s1 + len2 + i] = add(c[s1 + len2 + i], c[s3 + i]);
  98.     }
  99.    
  100.     return;
  101. }
  102.  
  103. void solve(int n)
  104.     {
  105.     for (int i = 0; i < n; i++)
  106.         {
  107.         a[2 * i] = sub(0, i);
  108.         a[2 * i + 1] = 1;
  109.     }
  110.     n *= 2;
  111.     for (int len = 2; len < n; len <<= 1)
  112.         {
  113.         for (int s = 0; s + (len << 1) <= n; s += (len << 1))
  114.             {
  115.             for (int i = 0; i < 2 * len; i++)
  116.                 b[i] = a[s + i];
  117.             multPoly(0, len, len);
  118.             for (int i = 0; i < 2 * len; i++)
  119.                 a[s + i] = c[i];
  120.         }
  121.         while(n % (len << 1)) n++;
  122.     }
  123.     return;
  124. }
  125.  
  126. int main() {
  127.     int n;
  128.     scanf("%d", &n);
  129.     solve(n);
  130.     /*
  131.     for (int i = 0; i <= n; i++)
  132.         printf("%d ", a[i]);
  133.     printf("\n");
  134.     */
  135.     for (int i = 1; i <= n; i += 2)
  136.         a[n - i] = sub(0, a[n - i]);
  137.     for (int i = 1; i < n; i++)
  138.         {
  139.         if (i >= 2)
  140.             a[n - i] = add(a[n - i], a[n - i + 2]);
  141.         printf("%d ", a[n - i]);
  142.     }
  143.     printf("\n");
  144.        
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement