結果
| 問題 | No.1960 Guruguru Permutation |
| ユーザー |
 sigma425
|
| 提出日時 | 2022-05-27 23:07:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 12 ms / 2,000 ms |
| コード長 | 5,495 bytes |
| コンパイル時間 | 2,108 ms |
| コンパイル使用メモリ | 198,980 KB |
| 最終ジャッジ日時 | 2025-01-29 16:17:14 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using uint = unsigned int;using ull = unsigned long long;#define rep(i,n) for(int i=0;i<int(n);i++)#define rep1(i,n) for(int i=1;i<=int(n);i++)#define per(i,n) for(int i=int(n)-1;i>=0;i--)#define per1(i,n) for(int i=int(n);i>0;i--)#define all(c) c.begin(),c.end()#define si(x) int(x.size())#define pb push_back#define eb emplace_back#define fs first#define sc secondtemplate<class T> using V = vector<T>;template<class T> using VV = vector<vector<T>>;template<class T,class U> bool chmax(T& x, U y){if(x<y){ x=y; return true; }return false;}template<class T,class U> bool chmin(T& x, U y){if(y<x){ x=y; return true; }return false;}template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}template<class T>V<T> Vec(size_t a) {return V<T>(a);}template<class T, class... Ts>auto Vec(size_t a, Ts... ts) {return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));}template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"{";for(const T& v:vc) o<<v<<",";o<<"}";return o;}constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }#ifdef LOCAL#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endlvoid dmpr(ostream& os){os<<endl;}template<class T,class... Args>void dmpr(ostream&os,const T&t,const Args&... args){os<<t<<" ~ ";dmpr(os,args...);}#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {"; \for(auto v: x) cerr << v << ","; cerr << "}" << endl;#else#define show(x) void(0)#define dump(x) void(0)#define shows(...) void(0)#endiftemplate<class D> D divFloor(D a, D b){return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);}template<class D> D divCeil(D a, D b) {return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);}template<unsigned int mod_>struct ModInt{using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr static uint mod = mod_;uint v;ModInt():v(0){}ModInt(ll _v):v(normS(_v%mod+mod)){}explicit operator bool() const {return v!=0;}static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1]static ModInt make(const uint &x){ModInt m; m.v=x; return m;}ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}ModInt operator-() const { return make(normS(mod-v)); }ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}ModInt operator/(const ModInt& b) const { return *this*b.inv();}ModInt& operator+=(const ModInt& b){ return *this=*this+b;}ModInt& operator-=(const ModInt& b){ return *this=*this-b;}ModInt& operator*=(const ModInt& b){ return *this=*this*b;}ModInt& operator/=(const ModInt& b){ return *this=*this/b;}ModInt& operator++(int){ return *this=*this+1;}ModInt& operator--(int){ return *this=*this-1;}template<class T> friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);}template<class T> friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);}template<class T> friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);}template<class T> friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);}ModInt pow(ll p) const {if(p<0) return inv().pow(-p);ModInt a = 1;ModInt x = *this;while(p){if(p&1) a *= x;x *= x;p >>= 1;}return a;}ModInt inv() const { // should be primereturn pow(mod-2);}// ll extgcd(ll a,ll b,ll &x,ll &y) const{// ll p[]={a,1,0},q[]={b,0,1};// while(*q){// ll t=*p/ *q;// rep(i,3) swap(p[i]-=t*q[i],q[i]);// }// if(p[0]<0) rep(i,3) p[i]=-p[i];// x=p[1],y=p[2];// return p[0];// }// ModInt inv() const {// ll x,y;// extgcd(v,mod,x,y);// return make(normS(x+mod));// }bool operator==(const ModInt& b) const { return v==b.v;}bool operator!=(const ModInt& b) const { return v!=b.v;}bool operator<(const ModInt& b) const { return v<b.v;}friend istream& operator>>(istream &o,ModInt& x){ll tmp;o>>tmp;x=ModInt(tmp);return o;}friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}};using mint = ModInt<998244353>;//using mint = ModInt<1000000007>;V<mint> fact,ifact,invs;mint Choose(int a,int b){if(b<0 || a<b) return 0;return fact[a] * ifact[b] * ifact[a-b];}void InitFact(int N){ //[0,N]N++;fact.resize(N);ifact.resize(N);invs.resize(N);fact[0] = 1;rep1(i,N-1) fact[i] = fact[i-1] * i;ifact[N-1] = fact[N-1].inv();for(int i=N-2;i>=0;i--) ifact[i] = ifact[i+1] * (i+1);rep1(i,N-1) invs[i] = fact[i-1] * ifact[i];}mint solve(int N,int L,int R){if(L+R > N){int M = L+R-N;return solve(L+R-M-M,L-M,R-M);}if(L < R) swap(L,R);mint res = 0;rep(k,R+1){res += Choose(L,k) * Choose(R,k) * fact[k];}for(int i=L+R+1;i<=N;i++) res *= i;return res;}int main(){cin.tie(0);ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !!cout << fixed << setprecision(20);InitFact(400000);int N,L,R; cin >> N >> L >> R;cout << solve(N,L,R) << endl;show(brute(N,L,R));}