#849358 (C++23) No.2130 分配方法の数え上げ mod 998244353

提出ソース

結果

問題	No.2130 分配方法の数え上げ mod 998244353
ユーザー	VvyLw
提出日時	2023-03-15 17:43:03
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	37 ms / 2,000 ms
コード長	13,643 bytes
コンパイル時間	3,613 ms
コンパイル使用メモリ	253,060 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-18 12:28:45
合計ジャッジ時間	5,720 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	2 ms 4,348 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	3 ms 4,348 KB
testcase_18	AC	5 ms 4,348 KB
testcase_19	AC	5 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	5 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	5 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	6 ms 4,348 KB
testcase_26	AC	2 ms 4,348 KB
testcase_27	AC	36 ms 4,348 KB
testcase_28	AC	2 ms 4,348 KB
testcase_29	AC	37 ms 4,348 KB
testcase_30	AC	2 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	2 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	2 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

// --------------------------------------------------------------------------------------------------------------

/*#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//*/

void wa_haya_exe() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
}

mt19937 Random() {
    random_device seed_gen;
    mt19937 engine {seed_gen()};
    return engine;
}

// --------------------------------------------------------------------------------------------------------------

// alias
template <class T> using V = vector<T>;
template <class T,class U> using P = pair<T,U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqr = priority_queue<T,vector<T>,greater<T>>;
using ll = long long;
using ld = long double;
using uint = unsigned;
using ul = unsigned long long;
using pi = P<int,int>;
using pl = P<ll,ll>;
using pd = P<ld,ld>;
using pc = P<char,char>;
using ps = P<string,string>;

// Input
template <class T> void scan(T& a) { cin >> a; }
template <class T,class U> void scan(P<T,U>& p) { scan(p.first); scan(p.second); }
template <class T> void scan(V<T>& a) { for(auto &i: a) scan(i); }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail) { scan(head); in(tail...); }
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define UL(...) ul __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)

// Output
template <class T> void print(const T& a) { cout << a; }
template <class T,class U> void print(const P<T,U>& p) { print(p.first); cout<<" "; print(p.second); }
template <class T> void print(const V<T>& a) { if(!a.empty()){ print(a[0]); for(auto i=a.begin(); ++i!=a.end();){ cout<<" "; print(*i); } } }
void out(){ cout<<endl; }
template <class T> void out(const T& t){ print(t); cout<<endl; }
template <class Head, class... Tail> void out(const Head& head, const Tail&... tail) { print(head); cout<<" "; out(tail...); }
#define fix(x) cout<<fixed<<setprecision(x);
#define Ende return;
#define fin(...) { out(__VA_ARGS__); Ende }

// YesNo System
#define Yes fin("Yes")
#define No fin("No")
#define YesNo(bool) if(bool) out("Yes"); else out("No");
#define YESNO(bool) if(bool) out("YES"); else out("NO");
#define yesno(bool) if(bool) out("yes"); else out("no");
inline void yes(bool ok, string yes, string no){ out(ok?yes:no); }

// constance
const int MOD=998244353;
const int M0D=1000000007;
const int INF=0x3fffffff;
const ll LINF=0x1fffffffffffffff;
const ld DINF=numeric_limits<ld>::infinity();
const double PI=acos(-1);

// for
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0; i<n; ++i)
#define rep2(i,n) for(ll i=0; i<n; ++i)
#define rep3(i,a,b) for(ll i=a; i<b; ++i)
#define rep4(i,a,b,c) for(ll i=a; i<b; i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rvp1(n) for(ll i=n-1; i>=0; i--)
#define rvp2(i,n) for(ll i=n-1; i>=0; i--)
#define rvp3(i,a,b) for(ll i=b-1; i>=a; i--)
#define rvp4(i,a,b,c) for(ll i=b-1; i>=a; i-=c)
#define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__)
#define all1(v) v.begin(),v.end()
#define all2(v,a) v.begin(),v.begin()+a
#define all3(v,a,b) v.begin()+a,v.begin()+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define each1(elem,v) for(auto &elem: v)
#define each2(x,y,v) for(auto &[x,y]: v)
#define each3(x,y,z,v) for(auto &[x,y,z]: v)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define sqrp1(n) for(ll i=0; i*i<n; ++i)
#define sqrp2(i,n) for(ll i=0; i*i<n; ++i)
#define sqrp3(i,a,b) for(ll i=a; i*i<b; ++i)
#define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__)
#define irp(it,v) for(auto it=v.begin(); it!=v.end(); ++it)
#define ir(it,v) for(auto it=v.begin(); it!=v.end();)
#define FE(v,f) for_each(all(v),f)

// vector
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size); in(name)
#define wec(type,name,h,...) vector<vector<type>> name(h,vector<type>(__VA_ARGS__))
#define Wec(type,name,h) vector<vector<type>> name(h)
#define WEC(type,name,h,w) vector<vector<type>> name(h,vector<type>(w)); in(name)
#define rall(v) v.rbegin(), v.rend()
#define rev(v) reverse(all(v))
#define Sort(v) sort(all(v))
#define Sortt(v) sort(rall(v))
#define Min(v) *min_element(all(v))
#define Max(v) *max_element(all(v))
#define LB(v,x) lower_bound(all(v),x)
#define UB(v,x) upper_bound(all(v),x)
#define rtt(v,idx) rotate(all(v,idx),v.end())
#define adf(v,res) adjacent_difference(all(v),res.begin())
#define psum(v,s) partial_sum(all(v),s.begin()); rtt(s,v.size())
#define vsum1(v) reduce(all(v),0LL)
#define vsum2(v,a) reduce(all(v,a),0LL)
#define vsum3(v,a,b) reduce(all(v,a,b),0LL)
#define vsum(...) overload3(__VA_ARGS__,vsum3,vsum2,vsum1)(__VA_ARGS__)
#define vdsum1(v) reduce(all(v),0.0L)
#define vdsum2(v,a) reduce(all(v,a),0.0LL)
#define vdsum3(v,a,b) reduce(all(v,a,b),0.0L)
#define vdsum(...) overload3(__VA_ARGS__,vdsum3,vdsum2,vdsum1)(__VA_ARGS__)
#define vmul1(v) reduce(all(v),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul2(v,a) reduce(all(v,a),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul3(v,a,b) reduce(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; })
#define vmul(...) overload3(__VA_ARGS__,vmul3,vmul2,vmul1)(__VA_ARGS__)
#define iot(a,init) iota(all(a),init)
#define ers(v,x) v.erase(remove(all(v),x),v.end())
#define unq(v) Sort(v);v.erase(unique(all(v)),v.end())
#define cp(v,w) copy(all(v),back_inserter(w))
#define smp(v,w,size,eng) sample(all(v),back_inserter(w),size,eng);
#define rpl(v,f,r) replace_if(all(v),f,r)
#define All(v,f) all_of(all(v),f)
#define Exist(v,f) any_of(all(v),f)
#define Find(v,x) find(all(v),x)
#define cntif(v,f) count_if(all(v),f)
template <class T> inline T Count(V<T>& v, ll x) {
    Sort(v);
    return UB(v,x)-LB(v,x);
}
template <class T> inline void vout(V<T>& v) { FE(v,[](T x){out(x);}); }

// renew max(old < new) or min(old > new)
template <class T> bool chmax(T& a, const T& b) { if (a<b) { a=b; return 1; } return 0; }
template <class T,class U> bool chmax(T& a, const U& b) { if (a<b) { a=b; return 1; } return 0; }
template <class T> bool chmin(T& a, const T& b) { if (a>b) { a=b; return 1; } return 0; }
template <class T,class U> bool chmin(T& a, const U& b) { if (a>b) { a=b; return 1; } return 0; }

// overflow
template <class T> bool overflow_if_add(T a, T b) { return (numeric_limits<T>::max() - a) < b; }
template <class T> bool overflow_if_mul(T a, T b) { return (numeric_limits<T>::max() / a) < b; }

// tips
#define elif else if
#define scp(a,x,b) a<=x&&x<=b
#define Mod(x,m) (x+m)%m
#define each_idx(el,v) &el-&v[0]
#define Ceil(x) ceil((ld)x)
#define PW(a,b) (ll)pow(a,b)
#define IP(v,u,init) inner_product(all(v),u.begin(),init)
#define Mid(a,b) midpoint(a,b)
#define dst(v,itr) distance(v.begin(),itr)
#define mp make_pair
#define mt make_tuple
#define bit_check(bit,tar) (tar>>bit)&1
#define popcnt(x) __builtin_popcountll(x)
#define str_rpl(s,a,b) regex_replace(s,regex(a),b)
#define ast(bool) assert(bool)

// min, max
#define key_min(map) map.begin()->first
#define key_max(map) map.rbegin()->first
#define set_min(set) *set.begin()
#define set_max(set) *set.rbegin()
template<class... T> constexpr auto mymin(T... a) {
    return min(initializer_list<common_type_t<T...>>{a...});
}
template<class... T> constexpr auto mymax(T... a) {
    return max(initializer_list<common_type_t<T...>>{a...});
}

/* Permutation Sample
template <class T> inline void nPr(V<T>& v) {
    Sort(v);
    do {out(v);} while(next_permutation(all(v)));
}//*/

/* Divisor Sample
template <class T> V<T> divisor(T n) {
    V<T> div;
    sqrp(i,1,n+1) {
        if(n%i==0) {
            div.emplace_back(i);
            if(i*i!=n) div.emplace_back(n/i);
        }
    }
    Sort(div);
    return div;
}//*/

/* Prime Sample
bool is_prime(ul n) {
    sqrp(i,2,n+1) if(n%i==0) return 0;
    return 1;
}//*/

// Siege of Eratosthenes
V<bool> SoE(ll n) {
    V<bool> prime(n+1,1);
    if(n>=0) prime[0]=0;
    if(n>=1) prime[1]=0;
    sqrp(i,2,n+1) {
        if(!prime[i]) continue;
        rep(j,i*i,n+1,i) prime[j]=0;
    }
    return prime;
}

/* Prime Factor Sample
template<class T> V<P<T,T>> prmfct(T n) {
    V<P<T,T>> res;
    rep(i,2,n+1) {
        if(n%i!=0) continue;
        T tmp=0;
        while(n%i==0) {
            tmp++;
            n/=i;
        }
        res.emplace_back(i,tmp);
    }
    if(n!=1) res.emplace_back(n,1);
    return res;
}//*/

/* BFS Sample
template <class T> inline void bfs(V<V<T>>& g, T start, V<bool>& visited) {
    queue<T> que;
    que.emplace(start);
    visited[start]=1;
    while(!que.empty()) {
        T v=que.front();
        que.pop();
        each(nv,g[v]) {
            if(!visited[nv]) {
                visited[nv]=1;
                que.emplace(nv);
            }
        }
    }
}//*/

/* DFS Sample
template <class T> inline void dfs(V<V<T>>& g, T v, V<bool>& visited) {
    visited[v]=1;
    each(nv,g[v]) if(!visited[nv]) dfs(g,nv,visited);
}//*/

// UnionFind-Tree
struct UnionFind {
    V<ll> par,sz;
    UnionFind(ll n) {
        par.resize(n,0);
        sz.resize(n,0);
        rep(n) makeTree(i);
    }
    void makeTree(ll x) {
        par[x]=x;
        sz[x]=1;
    }
    bool same(ll x, ll y) { return root(x)==root(y); }
    bool unite(ll x, ll y) {
        x=root(x); y=root(y);
        if(x==y) return 0;
        if(sz[x]>sz[y]) {
            par[y]=x;
            sz[x]+=sz[y];
        }
        else {
            par[x]=y;
            sz[y]+=sz[x];
        }
        return 1;
    }
    ll root(ll x) {
        if(x!=par[x]) par[x]=root(par[x]);
        return par[x];
    }
    ll size(ll x) { return sz[root(x)]; }
};

// mint
constexpr const int mod=MOD;
struct mint{
    uint num = 0;
    constexpr mint() noexcept {}
    constexpr mint(const mint &x) noexcept : num(x.num){}
    constexpr operator ll() const noexcept { return num; }
    constexpr mint& operator+=(mint x) noexcept { num += x.num; if(num >= mod) num -= mod; return *this; }
    constexpr mint& operator++() noexcept { if(num == mod - 1) num = 0; else num++; return *this; }
    constexpr mint operator++(int) noexcept { mint ans(*this); operator++(); return ans; }
    constexpr mint operator-() const noexcept { return mint(0) -= *this; }
    constexpr mint& operator-=(mint x) noexcept { if(num < x.num) num += mod; num -= x.num; return *this; }
    constexpr mint& operator--() noexcept { if(num == 0) num = mod - 1; else num--; return *this; }
    constexpr mint operator--(int) noexcept { mint ans(*this); operator--(); return ans; }
    constexpr mint& operator*=(mint x) noexcept { num = ul(num) * x.num % mod; return *this; }
    constexpr mint& operator/=(mint x) noexcept { return operator*=(x.inv()); }
    template<class T> constexpr mint(T x) noexcept {
        using U = typename conditional<sizeof(T) >= 4, T, int>::type;
        U y = x; y %= U(mod); if(y < 0) y += mod; num = uint(y);
    }
    template <class T> constexpr mint operator+(T x) const noexcept { return mint(*this) += x; }
    template <class T> constexpr mint& operator+=(T x) noexcept { return operator+=(mint(x)); }
    template <class T> constexpr mint operator-(T x) const noexcept { return mint(*this) -= x; }
    template <class T> constexpr mint& operator-=(T x) noexcept { return operator-=(mint(x)); }
    template <class T> constexpr mint operator*(T x) const noexcept { return mint(*this) *= x; }
    template <class T> constexpr mint& operator*=(T x) noexcept { return operator*=(mint(x)); }
    template <class T> constexpr mint operator/(T x) const noexcept { return mint(*this) /= x; }
    template <class T> constexpr mint& operator/=(T x) noexcept { return operator/=(mint(x)); }
    constexpr mint inv() const noexcept { ll x = 0, y = 0; extgcd(num, mod, x, y); return x; }
    static constexpr ll extgcd(ll a, ll b, ll &x, ll &y) noexcept { ll g = a; x = 1; y = 0; if(b){ g = extgcd(b, a % b, y, x); y -= a / b * x; } return g; }
    constexpr mint pow(ul x) const noexcept { mint ans = 1, cnt = *this; while(x){ if(x & 1) ans *= cnt; cnt *= cnt; x /= 2; } return ans; }
};
ostream& operator<<(ostream& os, const mint& m){ os << m.num; return os; }
/*V<mint> fac(1,1),inv(1,1);
void reserve(ll a){
    if(fac.size()>=a) return;
    if(a<fac.size()*2) a=fac.size()*2;
    if(a>=mod) a=mod;
    while(fac.size()<a) fac.emplace_back(fac.back()*mint(fac.size()));
    inv.resize(fac.size());
    inv.back()=fac.back().inv();
    for(ll i=inv.size()-1; !inv[i-1]; i--) inv[i-1]=inv[i]*i;
}
mint fact(ll n){ if(n<0) return 0; reserve(n + 1); return fac[n]; }
mint perm(ll n,ll r){
    if(r<0 || n<r) return 0;
    if(n>>24){ mint ans=1; rep(r) ans*=n--; return ans; }
    reserve(n+1); return fac[n]*inv[n-r];
}
mint comb(ll n,ll r){ if(r<0 || n<r) return 0; r=min(r,n-r); reserve(r+1); return perm(n,r)*inv[r]; }//*/

// --------------------------------------------------------------------------------------------------------------


void solve() {
    LL(n,m);
    mint sum=1,a=1,b=1;
    ll x=n;
    x%=MOD;
    rep(i,1,m) {
        a*=x;
        b*=i;
        sum+=(a/b);
        x=Mod(x-1,MOD);
    }
    out(mint(2).pow(n)-sum);
}

int main() {
    wa_haya_exe();
    /*INT(t); while(t--)//*/
    solve();
}

yukicoder

結果

テストケース

ソースコード