WA 的那个点要 500 ms 肯定是哪儿写错了啊。。
by hly1204 @ 2020-09-08 07:25:30
@[hly1204](/user/242973) ln部分我是直接拿的之前的板子，要炸估计也是exp，但是真不会调了（
by Ame__ @ 2020-09-08 07:27:36
解决了爆int的问题多过了两个点（
```cpp
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void read(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
#define mod 998244353
#define del(x , y) \
{ \
(x - y < 0 ? x - y + mod : x - y) \
}
// #define int long long
const int kato = 5e5 + 10;
int n , a[kato] , b[kato] , c[kato] , d[kato] , f[kato] , len4;
inline int quick_pow(int a , int b){
int res = 1;
for(; b ; b >>= 1 , a = 1LL * a * a % mod){
if(b & 1){
res = 1LL * res * a % mod;
}
}
return res % mod;
}
#define doit(n) \
{ \
len4 = 1; while(len4 <= n) len4 <<= 1; \
}
inline void NTT(int *y , int len , int opt){
int *rev = new int[len];
rev[0] = 0;
for(int i = 1;i < len;i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
for(int i = 0;i < len;i ++) if(i < rev[i]) swap(y[i] , y[rev[i]]);
for(int i = 1;i < len;i <<= 1){
int g1 = quick_pow(3 , (mod - 1) / (i << 1));
for(int j = 0;j < len;j += (i << 1)){
for(int k = 0 , g = 1;k < i;k ++ , g = g * 1LL * g1 % mod){
int res = y[i + k + j] * 1LL * g % mod;
y[i + k + j] = ((y[j + k] - res) % mod + mod) % mod;
y[j + k] = (y[j + k] + res) % mod;
}
}
}
if(opt == -1){
reverse(y + 1 , y + len);
for(int i = 0 , inv = quick_pow(len , mod - 2);i < len;i ++) y[i] = y[i] * 1LL * inv % mod;
}
delete []rev;
}
void poly_inv(int *a , int len){
if(len == 1){ a[0] = quick_pow(a[0] , mod - 2); return;}
int len1 = len / 2;
int *g = new int[len * 2];
for(int i = 0;i < len1;i ++) g[i] = a[i];
for(int i = len1;i < len * 2;i ++) g[i] = 0;
poly_inv(g , len1);
for(int i = len1;i < len * 2;i ++) g[i] = 0;
NTT(g , len * 2 , 1) , NTT(a , len * 2 , 1);
for(int i = 0;i < len * 2;i ++) a[i] = ((2 * g[i] % mod - 1LL * a[i] * g[i] % mod * g[i] % mod) % mod + mod) % mod;
NTT(a , len * 2 , -1);
for(int i = len1;i < len * 2;i ++) a[i] = 0;
delete []g;
}
inline void poly_mul(int *a , int *b , int len){
doit(len);
// while(len <= 2 * n) len <<= 1;
NTT(a , len4 , 1) , NTT(b , len4 , 1);
for(int i = 0;i < len4;i ++) a[i] = a[i] * 1LL * b[i] % mod;
NTT(a , len4 , -1);
}
inline void poly_dev(int *a , int *b , int len){
for(int i = 1;i < len;i ++) b[i - 1] = a[i] * 1LL * i % mod;
b[len - 1] = 0;
}
inline void poly_dev_inv(int *a , int *b , int len){
for(int i = 1;i < len;i ++) b[i] = a[i - 1] * 1LL * quick_pow(i , mod - 2) % mod;
b[0] = 0;
}
inline void get_ln(int *a , int *b , int len){
poly_dev(a , c , len);
// cout << "QWQ" << '\n';
// int cnt = 1; while(cnt <= 2 * n) cnt <<= 1;
for(int i = 0;i < n;i ++) { d[i] = a[i]; }
poly_inv(d , len * 2); poly_mul(c , d , len); poly_dev_inv(c , b , len);
for(int i = 0;i < len * 2;i ++) c[i] = d[i] = 0;
}
void exp(int *a , int *b , int len){
if(len == 1) return (void)(b[0] = 1);
exp(a , b , len >> 1) , get_ln(b , f , len);
f[0] = del(a[0] + 1 , f[0]);
for(int i = 1;i < len;i ++) f[i] = del(a[i] , f[i]);
NTT(f , len * 2 , 1) , NTT(b , len * 2 , 1);
for(int i = 0;i < len * 2;i ++) b[i] = 1LL * b[i] * f[i] % mod;
NTT(b , len * 2 , -1);
for(int i = len;i < len * 2;i ++) b[i] = f[i] = 0;
}
inline int Ame_(){
read(n);
for(int i = 0;i < n;i ++) read(a[i]);
// poly_inv(a , n);
int cnt = 1; while(cnt <= 2 * n) cnt <<= 1;
exp(a , b , cnt);
for(int i = 0;i < n;i ++) printf("%d " , b[i]);
printf("\n");
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
/*
6
0 927384623 817976920 427326948 149643566 610586717
*/
```
by Ame__ @ 2020-09-08 08:08:08
@[Ame__](/user/245875) 这样好像多过了几个点
```cpp
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void read(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
#define mod 998244353
#define del(x , y) \
{ \
(x - y < 0 ? x - y + mod : x - y) \
}
// #define int long long
const int kato = 5e5 + 10;
int n , a[kato] , b[kato] , c[kato] , d[kato] , f[kato] , len4;
inline int quick_pow(int a , int b){
int res = 1;
for(; b ; b >>= 1 , a = 1LL * a * a % mod){
if(b & 1){
res = 1LL * res * a % mod;
}
}
return res % mod;
}
#define doit(n) \
{ \
len4 = 1; while(len4 <= n) len4 <<= 1; \
}
inline void NTT(int *y , int len , int opt){
int *rev = new int[len];
rev[0] = 0;
for(int i = 1;i < len;i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
for(int i = 0;i < len;i ++) if(i < rev[i]) swap(y[i] , y[rev[i]]);
for(int i = 1;i < len;i <<= 1){
int g1 = quick_pow(3 , (mod - 1) / (i << 1));
for(int j = 0;j < len;j += (i << 1)){
for(int k = 0 , g = 1;k < i;k ++ , g = g * 1LL * g1 % mod){
int res = y[i + k + j] * 1LL * g % mod;
y[i + k + j] = ((y[j + k] - res) % mod + mod) % mod;
y[j + k] = (y[j + k] + res) % mod;
}
}
}
if(opt == -1){
reverse(y + 1 , y + len);
for(int i = 0 , inv = quick_pow(len , mod - 2);i < len;i ++) y[i] = y[i] * 1LL * inv % mod;
}
delete []rev;
}
void poly_inv(int *a , int len){
if(len == 1){ a[0] = quick_pow(a[0] , mod - 2); return;}
int len1 = len / 2;
int *g = new int[len * 2];
for(int i = 0;i < len1;i ++) g[i] = a[i];
for(int i = len1;i < len * 2;i ++) g[i] = 0;
poly_inv(g , len1);
for(int i = len1;i < len * 2;i ++) g[i] = 0;
NTT(g , len * 2 , 1) , NTT(a , len * 2 , 1);
for(int i = 0;i < len * 2;i ++) a[i] = ((2 * g[i] % mod - 1LL * a[i] * g[i] % mod * g[i] % mod) % mod + mod) % mod;
NTT(a , len * 2 , -1);
for(int i = len1;i < len * 2;i ++) a[i] = 0;
delete []g;
}
inline void poly_mul(int *a , int *b , int len){
doit(len);
// while(len <= 2 * n) len <<= 1;
NTT(a , len4 , 1) , NTT(b , len4 , 1);
for(int i = 0;i < len4;i ++) a[i] = a[i] * 1LL * b[i] % mod;
NTT(a , len4 , -1);
}
inline void poly_dev(int *a , int *b , int len){
for(int i = 1;i < len;i ++) b[i - 1] = a[i] * 1LL * i % mod;
b[len - 1] = 0;
}
inline void poly_dev_inv(int *a , int *b , int len){
for(int i = 1;i < len;i ++) b[i] = a[i - 1] * 1LL * quick_pow(i , mod - 2) % mod;
b[0] = 0;
}
inline void get_ln(int *a , int *b , int len){
poly_dev(a , c , len);
// cout << "QWQ" << '\n';
// int cnt = 1; while(cnt <= 2 * n) cnt <<= 1;
for(int i = 0;i < len;i ++) { d[i] = a[i]; }//这里把n改成len了
poly_inv(d , len * 2); poly_mul(c , d , len); poly_dev_inv(c , b , len);
for(int i = 0;i < len * 2;i ++) c[i] = d[i] = 0;
}
void exp(int *a , int *b , int len){
if(len == 1) return (void)(b[0] = 1);
exp(a , b , len >> 1) , get_ln(b , f , len);
f[0] = del(a[0] + 1 , f[0]);
for(int i = 1;i < len;i ++) f[i] = del(a[i] , f[i]);
NTT(f , len * 2 , 1) , NTT(b , len * 2 , 1);
for(int i = 0;i < len * 2;i ++) b[i] = 1LL * b[i] * f[i] % mod;
NTT(b , len * 2 , -1);
for(int i = len;i < len * 2;i ++) b[i] = f[i] = 0;
}
inline int Ame_(){
read(n);
for(int i = 0;i < n;i ++) read(a[i]);
// poly_inv(a , n);
int cnt = 1; while(cnt <= 2 * n) cnt <<= 1;
exp(a , b , cnt);
for(int i = 0;i < n;i ++) printf("%d " , b[i]);
printf("\n");
return ~~(0^_^0);
}
int [Ame__](/user/245875) = Ame_();
signed main(){;}
```
by mod998244353 @ 2020-09-08 12:39:07
@[mod998244353](/user/279646) 谢谢dalao了，已经de出来bug了，之前写的求逆元有个小错
by Ame__ @ 2020-09-08 13:51:22