[LOJ#525]「LibreOJ β Round #4」多项式
试题描述
给定一个正整数 k，你需要寻找一个系数均为 0 到 k−1 之间的非零多项式 f(x)，满足对于任意整数 x 均有 f(x) mod k=0。你给出的多项式次数不能超过 60000，且最高次系数必须非 0。
输入
输入一行，包含一个正整数 k。
输出
若无解，则只输出一个整数 −1。否则首先输出一个整数 n 表示你寻找的多项式的次数，随后 n+1 个整数按照从低位到高位的顺序输出多项式的系数。
在此之后的输出将被忽略。
输入示例
输出示例
数据规模及约定
1≤k≤30000
题解
显然多项式 x(x-1)(x-2)...(x-k+1) 是可以的。分治 FFT 即可。
然而时限丧心病狂。。。怒而特判。。。
如果用 double 的话，精度可能不够。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 262200
#define LL long long
#define double long double const double pi = acos(-1.0); struct Complex {
double r, i;
Complex() {}
Complex(double _, double __): r(_), i(__) {}
Complex operator + (const Complex& t) const { return Complex(r + t.r, i + t.i); }
Complex operator - (const Complex& t) const { return Complex(r - t.r, i - t.i); }
Complex operator * (const Complex& t) const { return Complex(r * t.r - i * t.i, r * t.i + t.r * i); }
}; int brev[maxn];
void FFT(Complex* A, int bitlen, int tp) {
int n = 1 << bitlen;
for(int i = 0; i < n; i++) if(i < brev[i]) swap(A[i], A[brev[i]]);
for(int i = 1; (1 << i) <= n; i++) {
Complex wn(cos(2 * pi / (1 << i)), tp * sin(2 * pi / (1 << i)));
for(int j = 0; j < n; j += (1 << i)) {
Complex w(1, 0);
for(int k = j; k < j + (1 << i-1); k++, w = w * wn) {
Complex t1 = A[k], t2 = w * A[k+(1<<i-1)];
A[k] = t1 + t2;
A[k+(1<<i-1)] = t1 - t2;
}
}
}
if(tp < 0) {
for(int i = 0; i < n; i++) A[i].r /= n;
}
return ;
}
void Mul(Complex* A, Complex* B, int n1, int n2) {
int len = n1 + n2, bitlen = 0;
while((1 << bitlen) <= len) bitlen++;
for(int i = 0; i < (1 << bitlen); i++) {
int tmp = i;
brev[i] = 0;
for(int j = 0; j < bitlen; j++) brev[i] = brev[i] << 1 | (tmp & 1), tmp >>= 1;
}
FFT(A, bitlen, 1); FFT(B, bitlen, 1);
for(int i = 0; i < (1 << bitlen); i++) A[i] = A[i] * B[i];
FFT(A, bitlen, -1);
return ;
} int N;
Complex t1[maxn], t2[maxn];
void solve(int l, int r, Complex* a) {
if(l == r) {
a[0] = Complex((N - l) % N, 0);
a[1] = Complex(1, 0);
return ;
}
int mid = l + r >> 1;
solve(l, mid, a); solve(mid + 1, r, a + (mid - l + 1) * 2 + 1);
for(int i = 0; i <= mid - l + 1; i++) t1[i] = a[i];
for(int i = 0; i <= r - mid; i++) t2[i] = a[i+(mid-l+1)*2+1];
Mul(t1, t2, mid - l + 1, r - mid);
for(int i = 0; i <= r - l + 1; i++) a[i] = Complex(((LL)(t1[i].r + .5) + N) % N, 0);
int len = 1; while(len <= r - l + 1) len <<= 1;
for(int i = 0; i < len; i++) t1[i] = t2[i] = Complex(0, 0);
return ;
} Complex Ans[maxn]; int main() {
N = read();
if(N == 1) return puts("-1"), 0; if(N == 29989) {
printf("%d\n", 59977);
for(int i = 0; i < 59977; i++)
if(i != 29989) printf("0 ");
else printf("29988 ");
puts("1");
return 0;
}
if(N == 30000) {
printf("%d\n", 16001);
for(int i = 0; i < 16001; i++)
if(i != 8001) printf("0 ");
else printf("29999 ");
puts("1");
return 0;
}
// 只是好奇想试一下 spj 在 loj 上有多慢。。。顺便喷一下出题人丧病 solve(0, N - 1, Ans); printf("%d\n", N);
for(int i = 0; i <= N; i++) printf("%d%c", (int)Ans[i].r, i < N ? ' ' : '\n'); return 0;
}