QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#184633 | #6736. Alice and Bob | bulijiojiodibuliduo# | AC ✓ | 415ms | 233108kb | C++ | 3.1kb | 2023-09-21 00:17:54 | 2023-09-21 00:17:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
template<int MOD, int RT> struct mint {
static const int mod = MOD;
static constexpr mint rt() { return RT; } // primitive root for FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint():v(0) {}
mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
bool operator==(const mint& o) const {
return v == o.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }
mint& operator+=(const mint& o) {
if ((v += o.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& o) {
if ((v -= o.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& o) {
v = int((ll)v*o.v%MOD); return *this; }
mint& operator/=(const mint& o) { return (*this) *= inv(o); }
friend mint pow(mint a, ll p) {
mint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
friend mint inv(const mint& a) { assert(a.v != 0);
return pow(a,MOD-2); }
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
};
const int MOD=998244353;
using mi = mint<MOD,5>; // 5 is primitive root for both common mods
namespace simp {
vector<mi> fac,ifac,invn;
void check(int x) {
if (fac.empty()) {
fac={mi(1),mi(1)};
ifac={mi(1),mi(1)};
invn={mi(0),mi(1)};
}
while (SZ(fac)<=x) {
int n=SZ(fac),m=SZ(fac)*2;
fac.resize(m);
ifac.resize(m);
invn.resize(m);
for (int i=n;i<m;i++) {
fac[i]=fac[i-1]*mi(i);
invn[i]=mi(MOD-MOD/i)*invn[MOD%i];
ifac[i]=ifac[i-1]*invn[i];
}
}
}
mi gfac(int x) {
check(x); return fac[x];
}
mi ginv(int x) {
check(x); return invn[x];
}
mi gifac(int x) {
check(x); return ifac[x];
}
mi binom(int n,int m) {
if (m < 0 || m > n) return mi(0);
return gfac(n)*gifac(m)*gifac(n - m);
}
}
int n;
mi ans;
int main() {
scanf("%d",&n);
for (int i=1;2*i-1<=n;i++) {
ans+=simp::binom(n-i,i-1)*simp::gfac(i-1)*simp::gfac(n-i);
}
printf("%d\n",(int)ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
10
output:
997920
result:
ok 1 number(s): "997920"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
100
output:
188898954
result:
ok 1 number(s): "188898954"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4
output:
10
result:
ok 1 number(s): "10"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
8
output:
12336
result:
ok 1 number(s): "12336"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
16
output:
373118483
result:
ok 1 number(s): "373118483"
Test #8:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
32
output:
314585464
result:
ok 1 number(s): "314585464"
Test #9:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
64
output:
627827331
result:
ok 1 number(s): "627827331"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
128
output:
828497685
result:
ok 1 number(s): "828497685"
Test #11:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
256
output:
65697890
result:
ok 1 number(s): "65697890"
Test #12:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
512
output:
854187619
result:
ok 1 number(s): "854187619"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
1024
output:
513823539
result:
ok 1 number(s): "513823539"
Test #14:
score: 0
Accepted
time: 44ms
memory: 31888kb
input:
1361956
output:
617368199
result:
ok 1 number(s): "617368199"
Test #15:
score: 0
Accepted
time: 212ms
memory: 118308kb
input:
7579013
output:
827172636
result:
ok 1 number(s): "827172636"
Test #16:
score: 0
Accepted
time: 214ms
memory: 118164kb
input:
8145517
output:
710624331
result:
ok 1 number(s): "710624331"
Test #17:
score: 0
Accepted
time: 177ms
memory: 118128kb
input:
6140463
output:
707600568
result:
ok 1 number(s): "707600568"
Test #18:
score: 0
Accepted
time: 87ms
memory: 60612kb
input:
3515281
output:
698302413
result:
ok 1 number(s): "698302413"
Test #19:
score: 0
Accepted
time: 204ms
memory: 118128kb
input:
6969586
output:
69470392
result:
ok 1 number(s): "69470392"
Test #20:
score: 0
Accepted
time: 69ms
memory: 60624kb
input:
2888636
output:
433579983
result:
ok 1 number(s): "433579983"
Test #21:
score: 0
Accepted
time: 385ms
memory: 233108kb
input:
9999998
output:
758172780
result:
ok 1 number(s): "758172780"
Test #22:
score: 0
Accepted
time: 415ms
memory: 232900kb
input:
9999999
output:
605195495
result:
ok 1 number(s): "605195495"
Test #23:
score: 0
Accepted
time: 388ms
memory: 232900kb
input:
10000000
output:
866813682
result:
ok 1 number(s): "866813682"