Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- const int MOD = (int)1e9 + 7;
- int add(int x, int y)
- {
- x += y;
- if (x >= MOD) return x - MOD;
- return x;
- }
- int sub(int x, int y)
- {
- x -= y;
- if (x < 0) return x + MOD;
- return x;
- }
- int mult(int x, int y)
- {
- return ((ll)x * y) % MOD;
- }
- const int LOG = 19;
- const int N = (1 << LOG) + 5;
- int a[N];
- int b[N << 1];
- int c[N << 1];
- const int L = 16;
- void printPoly(int* A, int len)
- {
- printf("{ ");
- for (int i = 0; i < len; i++)
- printf("%d ", A[i]);
- printf("}");
- }
- void multPoly(int s1, int s2, int len)
- {
- /*
- printPoly(b + s1, len);
- printf(" * ");
- printPoly(b + s2, len);
- printf("\n");
- */
- for (int i = s1; i < s1 + (len << 1); i++)
- c[i] = 0;
- if (len <= L)
- {
- for (int i = 0; i < len; i++)
- for (int j = 0; j < len; j++)
- {
- c[s1 + i + j] = add(c[s1 + i + j], mult(b[s1 + i], b[s2 + j]));
- }
- return;
- }
- int len2 = len >> 1;
- int s3 = s2 + len;
- int s4 = s3 + len2;
- for (int i = 0; i < len2; i++)
- {
- b[s3 + i] = b[s1 + i];
- b[s4 + i] = b[s2 + i];
- }
- multPoly(s3, s4, len2);
- for (int i = 0; i < len; i++)
- {
- c[s1 + i] = add(c[s1 + i], c[s3 + i]);
- c[s1 + len2 + i] = sub(c[s1 + len2 + i], c[s3 + i]);
- }
- for (int i = 0; i < len2; i++)
- {
- b[s3 + i] = b[s1 + len2 + i];
- b[s4 + i] = b[s2 + len2 + i];
- }
- multPoly(s3, s4, len2);
- for (int i = 0; i < len; i++)
- {
- c[s1 + len + i] = add(c[s1 + len + i], c[s3 + i]);
- c[s1 + len2 + i] = sub(c[s1 + len2 + i], c[s3 + i]);
- }
- for (int i = 0; i < len2; i++)
- {
- b[s3 + i] = add(b[s1 + i], b[s1 + len2 + i]);
- b[s4 + i] = add(b[s2 + i], b[s2 + len2 + i]);
- }
- multPoly(s3, s4, len2);
- for (int i = 0; i < len; i++)
- {
- c[s1 + len2 + i] = add(c[s1 + len2 + i], c[s3 + i]);
- }
- return;
- }
- void solve(int n)
- {
- for (int i = 0; i < n; i++)
- {
- a[2 * i] = sub(0, i);
- a[2 * i + 1] = 1;
- }
- n *= 2;
- for (int len = 2; len < n; len <<= 1)
- {
- for (int s = 0; s + (len << 1) <= n; s += (len << 1))
- {
- for (int i = 0; i < 2 * len; i++)
- b[i] = a[s + i];
- multPoly(0, len, len);
- for (int i = 0; i < 2 * len; i++)
- a[s + i] = c[i];
- }
- while(n % (len << 1)) n++;
- }
- return;
- }
- int main() {
- int n;
- scanf("%d", &n);
- solve(n);
- /*
- for (int i = 0; i <= n; i++)
- printf("%d ", a[i]);
- printf("\n");
- */
- for (int i = 1; i <= n; i += 2)
- a[n - i] = sub(0, a[n - i]);
- for (int i = 1; i < n; i++)
- {
- if (i >= 2)
- a[n - i] = add(a[n - i], a[n - i + 2]);
- printf("%d ", a[n - i]);
- }
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement