QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#610319 | #6811. Alice's Dolls | tosania | RE | 3ms | 58944kb | C++14 | 8.7kb | 2024-10-04 15:35:17 | 2024-10-04 15:35:18 |
Judging History
answer
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 300007;
const int gg = 3, ig = 332738118, img = 86583718;
const int mod = 998244353;
template <typename T>void read(T &x)
{
x = 0;
int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
}
ll qpow(ll a, ll b)
{
ll res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
namespace Poly
{
#define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
#define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
#define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
#define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了
typedef vector<int> poly;
const int G = 3;//根据具体的模数而定,原根可不一定不一样!!!
//一般模数的原根为 2 3 5 7 10 6
const int inv_G = qpow(G, mod - 2);
int RR[N], deer[2][19][N], inv[N];
void init(const int t) {//预处理出来NTT里需要的w和wn,砍掉了一个log的时间
for (int p = 1; p <= t; ++ p) {
int buf1 = qpow(G, (mod - 1) / (1 << p));
int buf0 = qpow(inv_G, (mod - 1) / (1 << p));
deer[0][p][0] = deer[1][p][0] = 1;
for (int i = 1; i < (1 << p); ++ i) {
deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆
deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
}
}
inv[1] = 1;
for (int i = 2; i <= (1 << t); ++ i)
inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
}
int NTT_init(int n) {//快速数论变换预处理
int limit = 1, L = 0;
while (limit <= n) limit <<= 1, L ++ ;
for (int i = 0; i < limit; ++ i)
RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
return limit;
}
void NTT(poly &A, int type, int limit) {//快速数论变换
A.resize(limit);
for (int i = 0; i < limit; ++ i)
if (i < RR[i])
swap(A[i], A[RR[i]]);
for (int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
int len = mid >> 1;
for (int pos = 0; pos < limit; pos += mid) {
int *wn = deer[type][j];
for (int i = pos; i < pos + len; ++ i, ++ wn) {
int tmp = 1ll * (*wn) * A[i + len] % mod;
A[i + len] = ck(A[i] - tmp + mod);
A[i] = ck(A[i] + tmp);
}
}
}
if (type == 0) {
for (int i = 0; i < limit; ++ i)
A[i] = 1ll * A[i] * inv[limit] % mod;
}
}
poly poly_mul(poly A, poly B) {//多项式乘法
int deg = A.size() + B.size() - 1;
int limit = NTT_init(deg);
poly C(limit);
NTT(A, 1, limit);
NTT(B, 1, limit);
for (int i = 0; i < limit; ++ i)
C[i] = 1ll * A[i] * B[i] % mod;
NTT(C, 0, limit);
C.resize(deg);
return C;
}
poly poly_inv(poly &f, int deg) {//多项式求逆
if (deg == 1)
return poly(1, qpow(f[0], mod - 2));
poly A(f.begin(), f.begin() + deg);
poly B = poly_inv(f, (deg + 1) >> 1);
int limit = NTT_init(deg << 1);
NTT(A, 1, limit), NTT(B, 1, limit);
for (int i = 0; i < limit; ++ i)
A[i] = B[i] * (2 - 1ll * A[i] * B[i] % mod + mod) % mod;
NTT(A, 0, limit);
A.resize(deg);
return A;
}
poly poly_dev(poly f) {//多项式求导
int n = f.size();
for (int i = 1; i < n; ++ i) f[i - 1] = 1ll * f[i] * i % mod;
return f.resize(n - 1), f;//f[0] = 0,这里直接扔了,从1开始
}
poly poly_idev(poly f) {//多项式求积分
int n = f.size();
for (int i = n - 1; i ; -- i) f[i] = 1ll * f[i - 1] * inv[i] % mod;
return f[0] = 0, f;
}
poly poly_ln(poly f, int deg) {//多项式求对数
poly A = poly_idev(poly_mul(poly_dev(f), poly_inv(f, deg)));
return A.resize(deg), A;
}
poly poly_exp(poly &f, int deg) {//多项式求指数
if (deg == 1)
return poly(1, 1);
poly B = poly_exp(f, (deg + 1) >> 1);
B.resize(deg);
poly lnB = poly_ln(B, deg);
for (int i = 0; i < deg; ++ i)
lnB[i] = ck(f[i] - lnB[i] + mod);
int limit = NTT_init(deg << 1);//n -> n^2
NTT(B, 1, limit), NTT(lnB, 1, limit);
for (int i = 0; i < limit; ++ i)
B[i] = 1ll * B[i] * (1 + lnB[i]) % mod;
NTT(B, 0, limit);
B.resize(deg);
return B;
}
poly poly_sqrt(poly &f, int deg) {//多项式开方
if (deg == 1) return poly(1, 1);
poly A(f.begin(), f.begin() + deg);
poly B = poly_sqrt(f, (deg + 1) >> 1);
poly IB = poly_inv(B, deg);
int limit = NTT_init(deg << 1);
NTT(A, 1, limit), NTT(IB, 1, limit);
for (int i = 0; i < limit; ++ i)
A[i] = 1ll * A[i] * IB[i] % mod;
NTT(A, 0, limit);
for (int i = 0; i < deg; ++ i)
A[i] = 1ll * (A[i] + B[i]) * inv[2] % mod;
A.resize(deg);
return A;
}
poly poly_pow(poly f, int k) {//多项式快速幂
f = poly_ln(f, f.size());
for (auto &x : f) x = 1ll * x * k % mod;
return poly_exp(f, f.size());
}
poly poly_cos(poly f, int deg) {//多项式三角函数(cos)
poly A(f.begin(), f.begin() + deg);
poly B(deg), C(deg);
for (int i = 0; i < deg; ++ i)
A[i] = 1ll * A[i] * img % mod;
B = poly_exp(A, deg);
C = poly_inv(B, deg);
int inv2 = qpow(2, mod - 2);
for (int i = 0; i < deg; ++ i)
A[i] = 1ll * (1ll * B[i] + C[i]) % mod * inv2 % mod;
return A;
}
poly poly_sin(poly f, int deg) {//多项式三角函数(sin)
poly A(f.begin(), f.begin() + deg);
poly B(deg), C(deg);
for (int i = 0; i < deg; ++ i)
A[i] = 1ll * A[i] * img % mod;
B = poly_exp(A, deg);
C = poly_inv(B, deg);
int inv2i = qpow(img << 1, mod - 2);
for (int i = 0; i < deg; ++ i)
A[i] = 1ll * (1ll * B[i] - C[i] + mod) % mod * inv2i % mod;
return A;
}
poly poly_arcsin(poly f, int deg) {
poly A(f.size()), B(f.size()), C(f.size());
A = poly_dev(f);
B = poly_mul(f, f);
for (int i = 0; i < deg; ++ i)
B[i] = minus(mod, B[i]);
B[0] = plus(B[0], 1);
C = poly_sqrt(B, deg);
C = poly_inv(C, deg);
C = poly_mul(A, C);
C = poly_idev(C);
return C;
}
poly poly_arctan(poly f, int deg) {
poly A(f.size()), B(f.size()), C(f.size());
A = poly_dev(f);
B = poly_mul(f, f);
B[0] = plus(B[0], 1);
C = poly_inv(B, deg);
C = poly_mul(A, C);
C = poly_idev(C);
return C;
}
}
using Poly::poly;
using Poly::poly_inv;
using Poly::poly_mul;
using Poly::poly_arcsin;
using Poly::poly_arctan;
ll n, m, x, k, type, p, q, jie[N], inv[N],njie[N];
poly f, g;
char s[N];
poly a;
poly solve_a(int l, int r) {
//cout<<l<<" "<<r<<endl;
if (r - l == 1){
if (l == 0){
return poly{1};
}
else
return poly{l, 1};
}
int mid = (l + r) / 2;
return poly_mul(solve_a(l, mid) , solve_a(mid, r)) ;
}
signed main()
{
Poly::init(18);//2^21 = 2,097,152,根据题目数据多项式项数的大小自由调整,注意大小需要跟deer数组同步(21+1=22)
read(n);
read(m);
{
int a, b;
read(a);
read(b);
p = a * qpow(b, mod - 2) % mod;
q = (1 - p + mod) % mod;
}
jie[0] = 1;
njie[0]=1;
for (int i = 1; i <= n+m; i++) {
jie[i] = jie[i - 1] *i%mod;
njie[i]=njie[i-1]*n%mod;
}
inv[n+m] = qpow(jie[n+m], mod - 2);
for (int i = n+m - 1; i >= 1; i--)
{
inv[i] = inv[i + 1] * (i+1) % mod;
}
inv[0]=1;
a = solve_a(0, n);
for (int i = 0; i <= n - 1; i++) {
a[i] *= inv[n - 1];
a[i] %= mod;
}
reverse(a.begin(), a.end());
poly s;
s.resize(n + m);
for (int i = 0; i < n + m; i++) {
s[i] = q * inv[i];
}
for (int i = 0; i < n + m; i++) {
if (i == 0)
s[i] = (1 - s[i]+mod)%mod;
else s[i] = (-s[i]+mod)%mod;
}
s = poly_inv(s, n + m);
for (int i = 0; i < n + m; i++) {
s[i] = (s[i] * jie[i]) % mod;
}
poly w = poly_mul(s, a);
for (int i = 0; i <= m; i++) {
w[i] = w[i + n - 1];
}
w.resize(m+1);
poly ans, op;
op.resize(m + 1);
for (int i = 0; i <= m; i++) {
op[i] = njie[i] * inv[i] % mod;
w[i] *= inv[i];
w[i]%=mod;
}
ans = poly_mul(op, w);
int A=qpow(p, n);
for (int i = 0; i <= m; i++) {
cout << ans[i]*jie[i] % mod*A % mod << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 58944kb
input:
1 3 1 2
output:
1 2 6 26
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 58876kb
input:
100 5 1 6
output:
1 600 363000 221433000 425510992 941092730
result:
ok 6 lines
Test #3:
score: -100
Runtime Error
input:
82346 94247 998244352 998244352