URL: http://acm.split.hdu.edu.cn/showproblem.php?pid=6061
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288
K (Java/Others) Total Submission(s): 702 Accepted Submission(s): 282
Problem Description
RXD has a polynomial function f(x), f(x)=∑ni=0cixi
RXD has a transformation of function Tr(f,a), it returns another function g, which has a property that g(x)=f(x−a).
Given a1,a2,a3,…,am, RXD generates a polynomial function sequence gi, in which g0=f and gi=Tr(gi−1,ai)
RXD wants you to find gm, in the form of ∑mi=0bixi
You need to output bi module 998244353.
n≤105
Input
There are several test cases, please keep reading until EOF.
For each test case, the first line consists of 1 integer n, which means degF.
The next line consists of n+1 intergers ci,0≤ci<998244353, which means the coefficient of the polynomial.
The next line contains an integer m, which means the length of a.
The next line contains m integers, the i - th integer is ai.
There are 11 test cases.
0<=ai<998244353
∑m≤105
Output
For each test case, output an polynomial with degree n, which means the answer.
Sample Input
2
0 0 1
1
1
Sample Output
1 998244351 1
Hint
(x−1)2=x2−2x+1
題解
待求表達式可以拆開然後化成 a(n)=∑ni=0h(i)g(i) 的形式
注意到隻要令 h′(x)=h(n−x) 就可到一個卷積式 (h⊗g)(n)=∑ni=0h′(n−i)g(i)
然後NTT
#include<stdio.h>
typedef long long LL;
const int MAXN = << ;
const int p = ( << ) + ;
const int g = ;
const int NUM = ;
int C[MAXN], A[MAXN], B[MAXN], fac[MAXN], wn[MAXN], n, m, len, S;
void swap(int &x, int &y) {
int t = x;
x = y;
y = t;
}
int mod_pow(int a, int k) {
int res = ;
while(k) {
if(k&) res = L * res * a % p;
a = L * a * a % p;
k >>= ;
}
return res;
}
void init() {
fac[] = ;
for(int i = ; i < MAXN; ++i) {
fac[i] = L * fac[i - ] * i % p;
}
for(int i = ; i < NUM; ++i) {
int t = << i;
wn[i] = mod_pow(g, (p - ) / t);
}
}
void rader(int y[]) {
for(int i = , j = len >> , k; i < len - ; ++ i) {
if(i < j) swap(y[i], y[j]);
k = len >> ;
while(j >= k) {
j -= k;
k >>= ;
}
if(j < k) j += k;
}
}
void NTT(int y[], int op) {
rader(y);
int id = ;
for(int h = ; h <= len; h <<= ) {
++id;
for(int i = ; i < len; i += h) {
int w = ;
for(int j = i; j < i + h / ; ++j) {
int u = y[j];
int t = L * w * y[j + h / ] % p;
y[j] = (u + t) % p;
y[j + h / ] = (u - t) % p;
w = L * w * wn[id] % p;
}
}
}
if(op == -) {
for(int i = ; i < len / ; ++i) {
swap(y[i], y[len - i]);
}
int inv = mod_pow(len, p - );
for(int i = ; i < len; ++i) {
y[i] = L * y[i] * inv % p;
y[i] += p;
y[i] %= p;
}
}
}
void slove() {
for(len = ; len < (n << ); len <<= ) ;
// printf("len: %d\n", len);
for(int i = ; i < len; ++i) {
A[i] = i > n ? : L * C[n - i] * fac[n - i] % p;
B[i] = i > n ? : L * mod_pow(S, i) * mod_pow(fac[i], p - ) % p;
// printf("#%d %d\n", C[i], B[i]);
}
NTT(A, );
NTT(B, );
for(int i = ; i < len; ++i) {
B[i] = L * A[i] * B[i] % p;
}
NTT(B, -);
int top = len - ;
while(top && !B[top]) --top;
for(int i = ; i <= n; ++i) {
int ans = L * B[n - i] * mod_pow(fac[i], p - ) % p;
printf(i == n ? "%d \n" : "%d ", ans);
}
}
int main()
{
init();
while(scanf("%d", &n) != EOF) {
for(int i = ; i <= n; ++i) {
scanf("%d", C + i);
}
scanf("%d", &m);
S = ;
for(int i = , a; i < m; ++i) {
scanf("%d", &a);
S -= a;
S += p;
S %= p;
}
slove();
}
return ;
}