QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#97470 | #6323. Range NEQ | Xingon | AC ✓ | 147ms | 108528kb | C++20 | 8.9kb | 2023-04-16 21:22:17 | 2023-04-16 21:22:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fp(i, a, b) for (int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e6 + 100, P = 998244353;
using ll = int64_t;
using Poly = vector<int>;
using MultiPoly = vector<Poly>;
//快读
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;
}
//二次剩余
/*---------------------------------------------------------------------------*/
class Cipolla {
int P, I2{};
using pll = pair<ll, ll>;
#define X first
#define Y second
ll mul(ll a, ll b) const { return a * b % P; }
pll mul(pll a, pll b) const { return { (a.X * b.X + I2 * a.Y % P * b.Y) % P, (a.X * b.Y + a.Y * b.X) % P }; }
template<class T> T POW(T a, int b, T x) { for (; b; b >>= 1, a = mul(a, a)) if (b & 1) x = mul(x, a); return x; }
public:
Cipolla(int p = 0) : P(p) {}
pair<int, int> sqrt(int n) {
int a = rand(), x;
if (!(n %= P)) return { 0, 0 };
if (POW(n, (P - 1) >> 1, 1ll) == P - 1) return { -1, -1 };
while (POW(I2 = ((ll)a * a - n + P) % P, (P - 1) >> 1, 1ll) == 1) a = rand();
x = (int)POW(pll{ a, 1 }, (P + 1) >> 1, { 1, 0 }).X;
if (2 * x > P) x = P - x;
return { x, P - x };
}
#undef X
#undef Y
};
/*---------------------------------------------------------------------------*/
#define MUL(a, b) (ll(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0) // (a += b) %= P
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P: 0) // ((a -= b) += P) %= P
//预处理L以内的逆元(0 ~ L-1)
Poly getInv(int L) { Poly inv(L); inv[1] = 1; fp(i, 2, L - 1) inv[i] = MUL((P - P / i), inv[P % i]); return inv; }
auto inv = getInv(N);
//快速幂
int qpow(ll a, int b = P - 2, ll x = 1) { for (; b; b >>= 1, a = a * a % P) if (b & 1) x = x * a % P; return x; }
/*---------------------------------------------------------------------------*/
namespace NTT {
const int g = 3;
Poly Omega(int L) {
int wn = qpow(g, P / L);
Poly w(L); w[L >> 1] = 1;
fp(i, L / 2 + 1, L - 1) w[i] = MUL(w[i - 1], wn);
fd(i, L / 2 - 1, 1) w[i] = w[i << 1];
return w;
}
auto W = Omega(1 << 23); // 注意这边的size,如果大于3e5,改成23;
void DIF(int* a, int n) {
for (int k = n >> 1; k; k >>= 1)
for (int i = 0, y; i < n; i += k << 1)
for (int j = 0; j < k; ++j)
y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
}
void IDIT(int* a, int n) {
for (int k = 1; k < n; k <<= 1)
for (int i = 0, x, y; i < n; i += k << 1)
for (int j = 0; j < k; ++j)
x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
int Inv = P - (P - 1) / n;
fp(i, 0, n - 1) a[i] = MUL(a[i], Inv);
reverse(a + 1, a + n);
}
}
namespace Polynomial {
// size确定以及NTT乘法
int norm(int n) { return 1 << ((int)log2(n - 1) + 1); }
void norm(Poly& a) { if (!a.empty()) a.resize(norm(a.size()), 0); else a = { 0 }; }
void DFT(Poly& a) { NTT::DIF(a.data(), a.size()); }
void IDFT(Poly& a) { NTT::IDIT(a.data(), a.size()); }
Poly& dot(Poly& a, Poly& b) { fp(i, 0, a.size() - 1) a[i] = MUL(a[i], b[i]); return a; }
// 和整数的乘除运算
Poly& operator*=(Poly& a, int b) { for (auto& x : a) x = MUL(x, b); return a; }
Poly operator*(Poly a, int b) { return a *= b; }
Poly operator*(int a, Poly b) { return b * a; }
Poly& operator/=(Poly& a, int b) { return a *= qpow(b); }
Poly operator/(Poly a, int b) { return a /= b; }
// 多项式之间的加减运算
Poly& operator+=(Poly& a, Poly b) {
a.resize(max(a.size(), b.size()));
fp(i, 0, b.size() - 1) ADD(a[i], b[i]);
return a;
}
Poly operator+(Poly a, Poly b) { return a += b; }
Poly& operator-=(Poly& a, Poly b) {
a.resize(max(a.size(), b.size()));
fp(i, 0, b.size() - 1) SUB(a[i], b[i]);
return a;
}
Poly operator-(Poly a, Poly b) { return a -= b; }
// 多项式乘法
Poly operator*(Poly a, Poly b) {
int n = a.size() + b.size() - 1, L = norm(n);
if (a.size() <= 30 || b.size() <= 30) {
Poly c(n);
fp(i, 0, a.size() - 1) fp(j, 0, b.size() - 1)
c[i + j] = (c[i + j] + (ll)a[i] * b[j]) % P;
return c;
}
a.resize(L), b.resize(L);
DFT(a), DFT(b), dot(a, b), IDFT(a);
return a.resize(n), a;
}
// 多项式逆元
Poly Inv2k(Poly a) { // |a| = 2 ^ k
int n = a.size(), m = n >> 1;
if (n == 1) return { qpow(a[0]) };
Poly b = Inv2k(Poly(a.begin(), a.begin() + m)), c = b;
b.resize(n), DFT(a), DFT(b), dot(a, b), IDFT(a);
fp(i, 0, n - 1) a[i] = i < m ? 0 : P - a[i];
DFT(a), dot(a, b), IDFT(a);
return move(c.begin(), c.end(), a.begin()), a;
}
Poly Inv(Poly a) {
int n = a.size();
norm(a), a = Inv2k(a);
return a.resize(n), a;
}
// 多项式除法/取模
Poly operator/(Poly a, Poly b) {
int k = a.size() - b.size() + 1;
if (k < 0) return { 0 };
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
b.resize(k), a = a * Inv(b);
a.resize(k), reverse(a.begin(), a.end());
return a;
}
pair<Poly, Poly> operator%(Poly a, const Poly& b) {
Poly c = a / b;
a -= b * c, a.resize(b.size() - 1);
return { c, a };
}
// 多项式求导积分
Poly deriv(Poly a) {
fp(i, 1, a.size() - 1) a[i - 1] = MUL(i, a[i]);
return a.pop_back(), a;
}
Poly integ(Poly a) {
a.push_back(0);
fd(i, a.size() - 1, 1) a[i] = MUL(inv[i], a[i - 1]);
return a[0] = 0, a;
}
// 取ln
Poly Ln(Poly a) {
int n = a.size();
a = deriv(a) * Inv(a);
return a.resize(n - 1), integ(a);
}
// 取exp
Poly Exp(Poly a) {
int n = a.size(), k = norm(n);
Poly b = { 1 }, c, d; a.resize(k);
for (int L = 2; L <= k; L <<= 1) {
d = b, b.resize(L), c = Ln(b), c.resize(L);
fp(i, 0, L - 1) c[i] = a[i] - c[i] + (a[i] < c[i] ? P : 0);
ADD(c[0], 1), DFT(b), DFT(c), dot(b, c), IDFT(b);
move(d.begin(), d.end(), b.begin());
}
return b.resize(n), b;
}
// 开根
Poly Sqrt(Poly a) {
int n = a.size(), k = norm(n); a.resize(k);
Poly b = { (new Cipolla(P))->sqrt(a[0]).first, 0 }, c;
for (int L = 2; L <= k; L <<= 1) {
b.resize(L), c = Poly(a.begin(), a.begin() + L) * Inv2k(b);
fp(i, L / 2, L - 1) b[i] = MUL(c[i], (P + 1) / 2);
}
return b.resize(n), b;
}
// 多项式快速幂
Poly Pow1(Poly& a, int b) { return Exp(Ln(a) * b); } // a[0] = 1, 循环卷积
Poly Pow2(Poly& a, int b) {
int n = (a.size() - 1) * b + 1, L = norm(n);
a.resize(L);
DFT(a);
fp(i, 0, L - 1) a[i] = qpow(a[i], b);
IDFT(a);
return a;
}
Poly Pow(Poly a, int b1, int b2) { // b1 = b % P, b2 = b % phi(P) and b >= n if a[0] > 0
int n = a.size(), d = 0, k;
while (d < n && !a[d]) ++d;
if ((ll)d * b1 >= n) return Poly(n);
a.erase(a.begin(), a.begin() + d);
k = qpow(a[0]), norm(a *= k);
a = Pow1(a, b1) * qpow(k, P - 1 - b2);
a.resize(n), d *= b1;
fd(i, n - 1, 0) a[i] = i >= d ? a[i - d] : 0;
return a;
}
}
using namespace Polynomial;
int infac[N], fac[N];
void init() {
infac[0] = fac[0] = 1;
for (int i = 1; i < N; i ++ ) {
fac[i] = fac[i - 1] * i % P;
infac[i] = infac[i - 1] * inv[i] % P;
}
}
int C(int a, int b) {
if (a < 0 || b < 0 || a < b) return 0;
return fac[a] * infac[b] % P * infac[a - b] % P;
}
int A(int a, int b) {
if (a < b || a < 0 || b < 0) return 0;
return fac[a] * infac[a - b] % P;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
int n, m;
cin >> n >> m;
Poly g(m + 1);
int ans = 0;
for(int i = 0; i <= m; ++i) g[i] = A(m, i) * C(m, i) % P;
Poly f = Pow2(g, n);
for (int i = 0; i <= n * m; i ++ ) {
if (i & 1) ans -= fac[n * m - i] * f[i] % P;
else ans += fac[n * m - i] * f[i] % P;
ans = (ans % P + P) % P;
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 48ms
memory: 92100kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 66ms
memory: 91988kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 54ms
memory: 92532kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 53ms
memory: 92024kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 46ms
memory: 92096kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 46ms
memory: 91980kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 44ms
memory: 91972kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 49ms
memory: 92036kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 51ms
memory: 91952kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 49ms
memory: 92060kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 50ms
memory: 92104kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 55ms
memory: 92188kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 55ms
memory: 92032kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 51ms
memory: 92036kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 57ms
memory: 92112kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 64ms
memory: 92044kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 53ms
memory: 91952kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: 0
Accepted
time: 147ms
memory: 108324kb
input:
1000 1000
output:
720037464
result:
ok 1 number(s): "720037464"
Test #19:
score: 0
Accepted
time: 60ms
memory: 91968kb
input:
72 42
output:
638177567
result:
ok 1 number(s): "638177567"
Test #20:
score: 0
Accepted
time: 48ms
memory: 92192kb
input:
15 19
output:
663050288
result:
ok 1 number(s): "663050288"
Test #21:
score: 0
Accepted
time: 58ms
memory: 92364kb
input:
68 89
output:
94365047
result:
ok 1 number(s): "94365047"
Test #22:
score: 0
Accepted
time: 52ms
memory: 92124kb
input:
92 37
output:
652605307
result:
ok 1 number(s): "652605307"
Test #23:
score: 0
Accepted
time: 65ms
memory: 92372kb
input:
61 87
output:
498277867
result:
ok 1 number(s): "498277867"
Test #24:
score: 0
Accepted
time: 46ms
memory: 91972kb
input:
81 40
output:
133095344
result:
ok 1 number(s): "133095344"
Test #25:
score: 0
Accepted
time: 52ms
memory: 92044kb
input:
7 91
output:
524164813
result:
ok 1 number(s): "524164813"
Test #26:
score: 0
Accepted
time: 50ms
memory: 91976kb
input:
31 18
output:
361233485
result:
ok 1 number(s): "361233485"
Test #27:
score: 0
Accepted
time: 54ms
memory: 92032kb
input:
74 54
output:
500686087
result:
ok 1 number(s): "500686087"
Test #28:
score: 0
Accepted
time: 56ms
memory: 92116kb
input:
32 2
output:
586504335
result:
ok 1 number(s): "586504335"
Test #29:
score: 0
Accepted
time: 80ms
memory: 100308kb
input:
656 718
output:
346764298
result:
ok 1 number(s): "346764298"
Test #30:
score: 0
Accepted
time: 79ms
memory: 96056kb
input:
254 689
output:
358078813
result:
ok 1 number(s): "358078813"
Test #31:
score: 0
Accepted
time: 93ms
memory: 100076kb
input:
713 674
output:
914437613
result:
ok 1 number(s): "914437613"
Test #32:
score: 0
Accepted
time: 50ms
memory: 94012kb
input:
136 698
output:
56687290
result:
ok 1 number(s): "56687290"
Test #33:
score: 0
Accepted
time: 69ms
memory: 96180kb
input:
369 401
output:
312325811
result:
ok 1 number(s): "312325811"
Test #34:
score: 0
Accepted
time: 62ms
memory: 92852kb
input:
280 204
output:
280012063
result:
ok 1 number(s): "280012063"
Test #35:
score: 0
Accepted
time: 73ms
memory: 96116kb
input:
904 225
output:
162909174
result:
ok 1 number(s): "162909174"
Test #36:
score: 0
Accepted
time: 122ms
memory: 108304kb
input:
855 928
output:
39885159
result:
ok 1 number(s): "39885159"
Test #37:
score: 0
Accepted
time: 75ms
memory: 96192kb
input:
503 365
output:
745115888
result:
ok 1 number(s): "745115888"
Test #38:
score: 0
Accepted
time: 133ms
memory: 108376kb
input:
646 996
output:
610925577
result:
ok 1 number(s): "610925577"
Test #39:
score: 0
Accepted
time: 143ms
memory: 108252kb
input:
990 918
output:
203469632
result:
ok 1 number(s): "203469632"
Test #40:
score: 0
Accepted
time: 145ms
memory: 108252kb
input:
961 949
output:
169566857
result:
ok 1 number(s): "169566857"
Test #41:
score: 0
Accepted
time: 132ms
memory: 108388kb
input:
946 932
output:
352423195
result:
ok 1 number(s): "352423195"
Test #42:
score: 0
Accepted
time: 142ms
memory: 108400kb
input:
903 981
output:
196309824
result:
ok 1 number(s): "196309824"
Test #43:
score: 0
Accepted
time: 125ms
memory: 108324kb
input:
916 988
output:
487208972
result:
ok 1 number(s): "487208972"
Test #44:
score: 0
Accepted
time: 138ms
memory: 108436kb
input:
982 982
output:
387421488
result:
ok 1 number(s): "387421488"
Test #45:
score: 0
Accepted
time: 138ms
memory: 108348kb
input:
955 911
output:
955637031
result:
ok 1 number(s): "955637031"
Test #46:
score: 0
Accepted
time: 144ms
memory: 108528kb
input:
906 999
output:
798469943
result:
ok 1 number(s): "798469943"
Test #47:
score: 0
Accepted
time: 139ms
memory: 108460kb
input:
982 975
output:
193506289
result:
ok 1 number(s): "193506289"
Test #48:
score: 0
Accepted
time: 141ms
memory: 108324kb
input:
921 991
output:
431202149
result:
ok 1 number(s): "431202149"