結果
問題 | No.1191 数え上げを愛したい(数列編) |
ユーザー | tatananonano |
提出日時 | 2023-04-06 00:36:25 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 7,860 bytes |
コンパイル時間 | 5,056 ms |
コンパイル使用メモリ | 265,412 KB |
実行使用メモリ | 12,932 KB |
最終ジャッジ日時 | 2024-04-27 04:34:32 |
合計ジャッジ時間 | 6,221 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
12,912 KB |
testcase_01 | AC | 10 ms
12,828 KB |
testcase_02 | AC | 11 ms
12,820 KB |
testcase_03 | AC | 9 ms
12,796 KB |
testcase_04 | AC | 10 ms
12,868 KB |
testcase_05 | AC | 11 ms
12,800 KB |
testcase_06 | AC | 11 ms
12,904 KB |
testcase_07 | AC | 10 ms
12,816 KB |
testcase_08 | AC | 10 ms
12,904 KB |
testcase_09 | AC | 10 ms
12,912 KB |
testcase_10 | AC | 10 ms
12,860 KB |
testcase_11 | AC | 9 ms
12,900 KB |
testcase_12 | AC | 11 ms
12,808 KB |
testcase_13 | AC | 12 ms
12,800 KB |
testcase_14 | AC | 11 ms
12,856 KB |
testcase_15 | AC | 11 ms
12,820 KB |
testcase_16 | AC | 11 ms
12,808 KB |
testcase_17 | AC | 10 ms
12,908 KB |
testcase_18 | AC | 10 ms
12,916 KB |
testcase_19 | AC | 11 ms
12,876 KB |
testcase_20 | AC | 10 ms
12,856 KB |
testcase_21 | AC | 11 ms
12,716 KB |
testcase_22 | AC | 10 ms
12,804 KB |
testcase_23 | AC | 10 ms
12,932 KB |
testcase_24 | AC | 9 ms
12,924 KB |
testcase_25 | AC | 9 ms
12,808 KB |
ソースコード
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <deque> #include <list> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <set> #include <map> #include <ctime> #include <stack> #include <functional> #include <cstdio> #include <string> #include <iostream> #include <limits> #include <stdexcept> #include <numeric> #include <fstream> #include <chrono> #include <utility> #include <cassert> #include <random> #include <time.h> #include <bitset> #include <sys/time.h> using namespace std; #define overload4(_1, _2, _3, _4, name, ...) name #define rep0(a) for (ll _ = 0; _ < ll(a); ++_) #define rep1(i, n) for (ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1,rep0)(__VA_ARGS__) #define rrep0(a) for (ll _ = (a)-1; _ >= ll(0); -- _) #define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--) #define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--) #define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d) #define drep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1,rrep0)(__VA_ARGS__) typedef long long ll; typedef unsigned long long ull; typedef long double LD; typedef double D; typedef pair<ll,ll> P; typedef map<ll,ll> M; // /* #include <atcoder/all> using namespace atcoder; //using namespace internal; using mint =modint998244353; //using mint =modint1000000007; //using mint=static_modint<4649>; #define ip(x) atcoder::internal::is_prime_constexpr(x) istream &operator>>(istream &is, mint &a) { int v; cin >> v; a = v; return is; } ostream &operator<<(ostream &os, const mint &a) { return os << a.val(); } auto v_pow(ll n,ll base){vector<mint> v(n,1);rep(i,n-1){v[i+1]*=base*v[i];}return v;} // */ template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; } template<class S, class T> istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; } template<class S, class T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; } template<class S, class T, class U> istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); } template<class S, class T, class U> ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';} #define YES(n) cout << ((n) ? "YES" : "NO" ) << endl #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define Game(n) cout << ((n) ? "First" : "Second" ) << endl template <typename F> ll binary_search(F check,ll ok,ll ng,bool border= true) { /*binary_search(bool_func,okな値,ngな値)*///しっかり区間内に... if(border) assert(check(ok)); while(abs(ok-ng)>1){ auto x=(ng+ok)/2; tie(ok,ng)=(check(x)?make_pair(x, ng):make_pair(ok, x)); } return ok; } template <typename F> double binary_search_real(F check,double ok,double ng,ll iter = 150) { rep(iter) { double x=(ok+ng)/2; tie(ok,ng)=(check(x)?make_pair(x,ng):make_pair(ok,x)); } return (ok+ng)/2; } void tatananonano() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout<< fixed << setprecision(10); } #define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; IN(__VA_ARGS__) #define INT(...) int __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;IN(__VA_ARGS__) #define LDL(...) LD __VA_ARGS__;IN(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;IN(__VA_ARGS__) #define vv(type, name, h, ...) \ vector<vector<type>> name(h, vector<type>(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector<vector<vector<type>>> name( \ h, vector<vector<type>>(w, vector<type>(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector<vector<vector<vector<type>>>> name( \ a, vector<vector<vector<type>>>( \ b, vector<vector<type>>(c, vector<type>(__VA_ARGS__)))) //#define MINT(...) mint __VA_ARGS__;IN(__VA_ARGS__) template <class T> void scan(T &a) { cin >> a; } void IN() {} template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {scan(head);IN(tail...);} #define overload2(_1, _2, _3,name, ...) name #define out1(x) cout<<x<<'\n' #define out2(x,y) cout<<x<<" "<<y<<'\n' #define out3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n' #define out4(x,y,z,w) cout<<x<<" "<<y<<" "<<z<<" "<<w<<'\n' #define out(...) overload4(__VA_ARGS__,out4,out3,out2,out1)(__VA_ARGS__) // #define each0(a) for(auto&&i:a) #define each1(i,a) for(auto&&i:a) #define each2(x,y,a) for(auto&&[x,y]:a) #define each3(x,y,z,a) for(auto&&[x,y,z]:a) #define each(...) overload4(__VA_ARGS__,each3,each2,each1,each0)(__VA_ARGS__) #define print1(x) cout<<x<<'\n' #define print2(x,n) cout<<fixed<<setprecision(n)<<x<<endl #define print3(x,n,empty) cout<<fixed<<setprecision(n)<<x<<" " #define print(...) overload2(__VA_ARGS__,print3,print2,print1)(__VA_ARGS__) #define bool_print(x,y1,y2) cout<<(x?y1:y2)<<'\n'; #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define MAX(a) *max_element(all(a)); #define MIN(a) *min_element(all(a)); #define pb push_back #define lb lower_bound #define ub upper_bound #define len(x) ll(x.size()) #define uni(x) sort(all(x));x.erase(unique(all(x)),x.end()) #define TFU(s) transform(all(s),begin(s),::toupper);//大文字にする #define TFL(s) transform(all(s),begin(s),::tolower);//小文字にする #define replace(s,a,A) replace(s,'a','A')//str(s)のaをAにする #define ROT(s,i) rotate(s.begin(),s.begin()+i,s.end())//sのi番目から後ろを前にする #define PQ priority_queue #define PQD PQ<P,vector<P>,greater<P>>//小さい順 #define PQS PQ<ll,vec,greater<ll>> #define fi first #define se second #define bit(n,k) ((n>>k)&1LL) #define popcount(n) __builtin_popcountll(n) template<class T> inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;} template<class T> inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;} template<class T> bool in_rect(T i,T j,T h,T w) {return 0 <= i and i < h and 0 <= j and j < w;} template<class T> bool is_in(T x,T a,T b){return (a<=x and x<b);} typedef vector<ll> vec; typedef vector<string> vs; using mat = vector<vec>; // template <typename T> using matrix = vector<vector<T>>; const ll mod = 998244353; //const ll mod = 1000000007; const auto INF = (1LL<<(60)); template <typename T, typename U> T ceil(T x, U y) {return (x > 0 ? (x + y - 1) / y : x / y);} template <typename T, typename U> T floor(T x, U y) {return (x > 0 ? x / y : (x - y + 1) / y);} D getTime() { struct timeval s; gettimeofday(&s, NULL); return s.tv_sec + s.tv_usec * 1e-6; } constexpr ll MAX = 400000; ll fac[MAX],finv[MAX],inv[MAX]; void cominit(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<MAX;i++){ fac[i]=fac[i-1]*i%mod; inv[i]=mod-inv[mod%i]*(mod/i)%mod; finv[i]=finv[i-1]*inv[i]%mod; } } /* ll binom(ll n,ll k){ if(n<k) return 0; if(n<0||k<0) return 0; return fac[n]*(finv[k]*finv[n-k]%mod)%mod; } */ ll POM(ll n,ll k){ if(n<k) return 0; return fac[n]*finv[n-k]%mod; } mint binom(ll n,ll k){ if(n<k) return 0; if(n<0||k<0) return 0; return mint(fac[n]*(mint(finv[k]*finv[n-k]))); } int main(){ tatananonano(); cominit(); LL(n,m,a,b); mint ans=0; rep(x,0,b-a*(n-1)+1){ ans+=(m-x-a*(n-1))*binom(n+x-2,n-2); } ans*=POM(n,n); cout<<ans<<endl; }