- 注册时间
- 2008-11-6
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 1483
- 在线时间
- 小时
|
发表于 2025-9-19 15:47:13
|
显示全部楼层
- #pragma GCC optimize("Ofast")
- #include<iostream>
- #include<cstring>
- using U = unsigned;
- using V = unsigned long long;
- constexpr U P = 998244353, N = 1 << 21;
- constexpr U F(U a, U b)
- {
- U c = 1;
- for (; b; b /= 2)
- b & 1 && (c = (V)c*a%P), a = (V)a*a%P;
- return c;
- }
- U R[N], T[N]{ 0,1 };
- void f(U*a) {
- for (U b = 1; b^N; b++)
- if (R[b] < b)
- a[b] ^= a[R[b]] ^= a[b] ^= a[R[b]];
- for (U b = 1, c, d, e, f; b^N; b *= 2)
- for (c = 0; c^N; c += b * 2)
- for (d = 0; d^b; d++)
- e = a[c + d], f = (V)a[b + c + d] * T[b + d] % P, (a[c + d] = e + f) >= P && (a[c + d] -= P), (a[b + c + d] = e - f) >= P && (a[b + c + d] += P);
- }
- main() {
- for (U a = 1; a^N; a++)
- R[a] = (R[a / 2] + a % 2 * N) / 2;
- for (U a = 2, b, c; a^N; a *= 2)
- for (b = F(3, P / a / 2), c = a / 2; c^a; c++)
- T[c * 2] = T[c], T[c * 2 + 1] = (V)T[c] * b%P;
- std::cin.tie(0)->sync_with_stdio(0);
- U a, b, c[N]{}, d[N]{};
- char x[N], y[N];
- std::cin >> x >> y, a = strlen(x) - 1, b = strlen(y) - 1;
- for (U e = 0; e <= a; e++)
- c[e] = x[a - e] ^ 48;
- for (U e = 0; e <= b; e++)
- d[e] = y[b - e] ^ 48;
- f(c), f(d);
- for (U e = 0; e^N; e++)
- c[e] = (V)c[e] * d[e] % P; f(c);
- a += b + 1;
- for (U e = *d = 0, f = F(N, P - 2); e^a; e++)
- d[e] += (V)c[(N - e) % N] * f%P, d[e + 1] = d[e] / 10, d[e] %= 10;
- while (!d[a])a--;
- for (; ~a; a--)
- std::cout << d[a];
- }
复制代码
写着代码的人怎么没被打死?!  
|
|