QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#610337 | #6811. Alice's Dolls | tosania | AC ✓ | 264ms | 139688kb | C++14 | 8.7kb | 2024-10-04 15:38:37 | 2024-10-04 15:38:38 |
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 = 800007;
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][20][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(19);//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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 108076kb
input:
1 3 1 2
output:
1 2 6 26
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 7ms
memory: 106028kb
input:
100 5 1 6
output:
1 600 363000 221433000 425510992 941092730
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 217ms
memory: 129712kb
input:
82346 94247 998244352 998244352
output:
1 82346 791397598 40508009 538125741 435438716 697592329 964874802 317657163 799962739 585095577 16686097 449113834 769228973 331835396 374844347 218958949 104110468 158094364 333890471 898754640 11498373 509376414 878962890 373081322 784577837 472039442 921273818 635966440 395465507 275355856 33108...
result:
ok 94248 lines
Test #4:
score: 0
Accepted
time: 244ms
memory: 139688kb
input:
99999 99998 1 1
output:
1 99999 17356471 681058015 897702913 273664856 341242002 872239399 469072873 314324010 366733079 438370760 733355951 836839610 300048400 309433479 458256580 792718955 518709315 637964452 7124024 647052287 379174959 801465042 656610000 821071425 723394325 932065530 543939213 40810170 153274766 279529...
result:
ok 99999 lines
Test #5:
score: 0
Accepted
time: 7ms
memory: 106092kb
input:
234 459 8713247 74362439
output:
1 550308667 652601851 21862568 312504180 301781771 955945774 241922434 687893799 220084008 951866075 223169979 261547613 851721240 108461996 645670062 647827677 740281647 567424949 65300355 783187507 824238091 706909540 715519504 74795499 263740113 795953643 525222901 990470578 720139891 531988015 3...
result:
ok 460 lines
Test #6:
score: 0
Accepted
time: 249ms
memory: 137760kb
input:
100000 100000 34457 34458
output:
1 110072884 866073590 736351474 206840805 363851986 895119597 144145068 753578218 113903056 711499733 430574479 231258052 694514889 284319691 530696819 535538312 933991851 868518537 888564382 239789947 182502325 355499336 74503434 691778894 327131524 233789093 41501704 639617307 916312185 394659685 ...
result:
ok 100001 lines
Test #7:
score: 0
Accepted
time: 264ms
memory: 135592kb
input:
100000 100000 998244351 998244352
output:
1 50000 503486294 85094752 335515298 331724101 676123256 80958981 314512322 659052656 12751483 516505166 655297143 652329290 347750398 78055519 290808848 35067066 791903803 995363140 517288436 394436580 430863665 823972579 523698332 746439583 27677016 323067719 660639896 110677907 568717926 25289325...
result:
ok 100001 lines
Test #8:
score: 0
Accepted
time: 148ms
memory: 122348kb
input:
93248 34 1 499122177
output:
1 46624 177285358 111979882 696375359 818605358 237802954 608377035 863173334 196258366 607718397 364819065 360314917 233450239 952902294 131353496 959526592 687802720 477763385 488883348 507982668 818592811 76520370 194416851 590074140 13328434 672264252 42015845 921175397 849890303 603093773 61302...
result:
ok 35 lines
Test #9:
score: 0
Accepted
time: 60ms
memory: 122612kb
input:
53 99997 2394 7681238
output:
1 955048736 470514326 41111193 709347504 116606594 22612570 620495230 589459109 278168830 277523111 890862369 212779039 908656172 927315643 325078855 630813446 435720817 357034897 545024798 456613789 312453851 69393505 463880280 934933770 586168348 444543516 547460238 575392663 993322173 625521110 7...
result:
ok 99998 lines
Test #10:
score: 0
Accepted
time: 141ms
memory: 135428kb
input:
100000 0 123456789 234567890
output:
1
result:
ok single line: '1'