QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152299 | #6323. Range NEQ | aesthetic# | AC ✓ | 1160ms | 226796kb | C++14 | 5.1kb | 2023-08-27 23:26:58 | 2023-08-27 23:26:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
typedef complex<double> C;
typedef vector<double> vd;
const ll inf=LLONG_MAX;
const int maxn=1e6+10;
const int md=998244353;
void fft(vector<C>& a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vector<complex<long double>> R(2, 1);
static vector<C> rt(2, 1); // (^ 10% faster if double)
for (static int k = 2; k < n; k *= 2) {
R.resize(n); rt.resize(n);
auto x = polar(1.0L, acos(-1.0L) / k);
rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
}
vi rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled) /// include-line
auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k]; /// exclude-line
C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]); /// exclude-line
a[i + j + k] = a[i + j] - z;
a[i + j] += z;
}
}
vd conv(const vd& a, const vd& b) {
if (a.empty() || b.empty()) return {};
vd res(sz(a) + sz(b) - 1);
int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
vector<C> in(n), out(n);
copy(all(a), begin(in));
rep(i,0,sz(b)) in[i].imag(b[i]);
fft(in);
for (C& x : in) x *= x;
rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
fft(out);
rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
return res;
}
typedef vector<ll> vl;
vl convMod(const vl &a, const vl &b) {
if (a.empty() || b.empty()) return {};
vl res(sz(a) + sz(b) - 1);
int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(md));
vector<C> L(n), R(n), outs(n), outl(n);
rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);
rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);
fft(L), fft(R);
rep(i,0,n) {
int j = -i & (n - 1);
outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i;
}
fft(outl), fft(outs);
rep(i,0,sz(res)) {
ll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5);
ll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5);
res[i] = ((av % md * cut + bv) % md * cut + cv) % md;
}
return res;
}
int fac[maxn], inv_fac[maxn];
int modInv(int a, int m)
{
int m0=m;
int y=0, x=1;
if(m==1)
return 0;
while(a>1)
{
int q=a/m;
int t=m;
m=a%m, a=t;
t=y;
y=x-q*y;
x=t;
}
if(x<0)
x+=m0;
return x;
}
int bc(int n, int k)
{
if (n<k || k<0) return 0;
return fac[n]*inv_fac[k]%md*inv_fac[n-k]%md;
}
ll pw(ll b, ll e)
{
ll ans=1;
for(; e; b=b*b%md, e/=2)
if(e&1)
ans=ans*b%md;
return (ans+md)%md;
}
int n, m;
vector<int> polys[1010];
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ios::sync_with_stdio(0);cin.tie(0);
fac[0]=1, inv_fac[0]=1;
for (int i=1; i<maxn; i++) {
fac[i]=fac[i-1]*i%md;
}
inv_fac[maxn-1]=modInv(fac[maxn-1], md);
for (int i=maxn-2; i>=1; i--) {
inv_fac[i]=inv_fac[i+1]*(i+1)%md;
}
cin>> n>> m;
vector<int> a(m+1);
for(int i=0; i<=m; i++)
{
a[i]=bc(m, i)*bc(m, i)%md*fac[i]%md;
// cout<< i<<" " << a[i]<< "\n";
}
// for(int x: a)
// cout<< x<< " ";
// cout<< "\n";
//quero b=a^n
for(int i = 1; i <= n; ++i)
polys[i] = a;
for(int sz = 2; sz <= 2*n; sz *= 2)
for(int i = 1; i+sz/2 <= n; i += sz)
polys[i] = convMod(polys[i], polys[i + sz / 2]);
vector<int> b = polys[1];
// for(int x: b)
// cout<< x<<" ";
// cout<< "\n";
int ans=fac[m*n];
for(int i=1; i<=m*n; i++)
{
ans+=(i%2?md-1:1)*b[i]%md*fac[m*n-i]%md;
// cout<< i<< " "<< b[i]*fac[m*n-i]%md<< "\n";
if(ans>=md)
ans-=md;
}
cout<< ans<< "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 19164kb
input:
2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 12ms
memory: 19096kb
input:
5 1
output:
44
result:
ok 1 number(s): "44"
Test #3:
score: 0
Accepted
time: 16ms
memory: 21816kb
input:
167 91
output:
284830080
result:
ok 1 number(s): "284830080"
Test #4:
score: 0
Accepted
time: 9ms
memory: 19088kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 11ms
memory: 19148kb
input:
2 3
output:
36
result:
ok 1 number(s): "36"
Test #6:
score: 0
Accepted
time: 6ms
memory: 19204kb
input:
2 4
output:
576
result:
ok 1 number(s): "576"
Test #7:
score: 0
Accepted
time: 11ms
memory: 19204kb
input:
3 1
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 6ms
memory: 19156kb
input:
3 2
output:
80
result:
ok 1 number(s): "80"
Test #9:
score: 0
Accepted
time: 11ms
memory: 19136kb
input:
3 3
output:
12096
result:
ok 1 number(s): "12096"
Test #10:
score: 0
Accepted
time: 11ms
memory: 19208kb
input:
3 4
output:
4783104
result:
ok 1 number(s): "4783104"
Test #11:
score: 0
Accepted
time: 6ms
memory: 19212kb
input:
4 1
output:
9
result:
ok 1 number(s): "9"
Test #12:
score: 0
Accepted
time: 8ms
memory: 19152kb
input:
4 2
output:
4752
result:
ok 1 number(s): "4752"
Test #13:
score: 0
Accepted
time: 12ms
memory: 19156kb
input:
4 3
output:
17927568
result:
ok 1 number(s): "17927568"
Test #14:
score: 0
Accepted
time: 11ms
memory: 19100kb
input:
4 4
output:
776703752
result:
ok 1 number(s): "776703752"
Test #15:
score: 0
Accepted
time: 12ms
memory: 19132kb
input:
5 2
output:
440192
result:
ok 1 number(s): "440192"
Test #16:
score: 0
Accepted
time: 11ms
memory: 19184kb
input:
5 3
output:
189125068
result:
ok 1 number(s): "189125068"
Test #17:
score: 0
Accepted
time: 7ms
memory: 19168kb
input:
5 4
output:
975434093
result:
ok 1 number(s): "975434093"
Test #18:
score: 0
Accepted
time: 1135ms
memory: 226796kb
input:
1000 1000
output:
720037464
result:
ok 1 number(s): "720037464"
Test #19:
score: 0
Accepted
time: 7ms
memory: 19512kb
input:
72 42
output:
638177567
result:
ok 1 number(s): "638177567"
Test #20:
score: 0
Accepted
time: 4ms
memory: 19172kb
input:
15 19
output:
663050288
result:
ok 1 number(s): "663050288"
Test #21:
score: 0
Accepted
time: 12ms
memory: 20252kb
input:
68 89
output:
94365047
result:
ok 1 number(s): "94365047"
Test #22:
score: 0
Accepted
time: 7ms
memory: 19516kb
input:
92 37
output:
652605307
result:
ok 1 number(s): "652605307"
Test #23:
score: 0
Accepted
time: 15ms
memory: 20136kb
input:
61 87
output:
498277867
result:
ok 1 number(s): "498277867"
Test #24:
score: 0
Accepted
time: 9ms
memory: 19600kb
input:
81 40
output:
133095344
result:
ok 1 number(s): "133095344"
Test #25:
score: 0
Accepted
time: 8ms
memory: 19188kb
input:
7 91
output:
524164813
result:
ok 1 number(s): "524164813"
Test #26:
score: 0
Accepted
time: 4ms
memory: 19292kb
input:
31 18
output:
361233485
result:
ok 1 number(s): "361233485"
Test #27:
score: 0
Accepted
time: 5ms
memory: 19612kb
input:
74 54
output:
500686087
result:
ok 1 number(s): "500686087"
Test #28:
score: 0
Accepted
time: 5ms
memory: 19172kb
input:
32 2
output:
586504335
result:
ok 1 number(s): "586504335"
Test #29:
score: 0
Accepted
time: 591ms
memory: 119448kb
input:
656 718
output:
346764298
result:
ok 1 number(s): "346764298"
Test #30:
score: 0
Accepted
time: 191ms
memory: 61812kb
input:
254 689
output:
358078813
result:
ok 1 number(s): "358078813"
Test #31:
score: 0
Accepted
time: 684ms
memory: 119600kb
input:
713 674
output:
914437613
result:
ok 1 number(s): "914437613"
Test #32:
score: 0
Accepted
time: 101ms
memory: 40996kb
input:
136 698
output:
56687290
result:
ok 1 number(s): "56687290"
Test #33:
score: 0
Accepted
time: 146ms
memory: 60400kb
input:
369 401
output:
312325811
result:
ok 1 number(s): "312325811"
Test #34:
score: 0
Accepted
time: 49ms
memory: 30788kb
input:
280 204
output:
280012063
result:
ok 1 number(s): "280012063"
Test #35:
score: 0
Accepted
time: 190ms
memory: 67128kb
input:
904 225
output:
162909174
result:
ok 1 number(s): "162909174"
Test #36:
score: 0
Accepted
time: 1017ms
memory: 209944kb
input:
855 928
output:
39885159
result:
ok 1 number(s): "39885159"
Test #37:
score: 0
Accepted
time: 190ms
memory: 64124kb
input:
503 365
output:
745115888
result:
ok 1 number(s): "745115888"
Test #38:
score: 0
Accepted
time: 806ms
memory: 192644kb
input:
646 996
output:
610925577
result:
ok 1 number(s): "610925577"
Test #39:
score: 0
Accepted
time: 1147ms
memory: 219548kb
input:
990 918
output:
203469632
result:
ok 1 number(s): "203469632"
Test #40:
score: 0
Accepted
time: 1160ms
memory: 218368kb
input:
961 949
output:
169566857
result:
ok 1 number(s): "169566857"
Test #41:
score: 0
Accepted
time: 1121ms
memory: 216776kb
input:
946 932
output:
352423195
result:
ok 1 number(s): "352423195"
Test #42:
score: 0
Accepted
time: 1078ms
memory: 216516kb
input:
903 981
output:
196309824
result:
ok 1 number(s): "196309824"
Test #43:
score: 0
Accepted
time: 1066ms
memory: 219056kb
input:
916 988
output:
487208972
result:
ok 1 number(s): "487208972"
Test #44:
score: 0
Accepted
time: 1083ms
memory: 223916kb
input:
982 982
output:
387421488
result:
ok 1 number(s): "387421488"
Test #45:
score: 0
Accepted
time: 1059ms
memory: 216348kb
input:
955 911
output:
955637031
result:
ok 1 number(s): "955637031"
Test #46:
score: 0
Accepted
time: 1085ms
memory: 219084kb
input:
906 999
output:
798469943
result:
ok 1 number(s): "798469943"
Test #47:
score: 0
Accepted
time: 1083ms
memory: 223424kb
input:
982 975
output:
193506289
result:
ok 1 number(s): "193506289"
Test #48:
score: 0
Accepted
time: 1122ms
memory: 219512kb
input:
921 991
output:
431202149
result:
ok 1 number(s): "431202149"