結果

問題 No.2561 みんな大好きmod 998
ユーザー uetaueta
提出日時 2023-12-02 14:45:46
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 681 ms / 4,000 ms
コード長 8,819 bytes
コンパイル時間 5,721 ms
コンパイル使用メモリ 164,996 KB
実行使用メモリ 327,272 KB
最終ジャッジ日時 2024-09-26 17:19:21
合計ジャッジ時間 13,243 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
11,648 KB
testcase_01 AC 30 ms
24,172 KB
testcase_02 AC 8 ms
11,648 KB
testcase_03 AC 577 ms
327,140 KB
testcase_04 AC 579 ms
327,012 KB
testcase_05 AC 664 ms
327,140 KB
testcase_06 AC 662 ms
327,144 KB
testcase_07 AC 7 ms
11,740 KB
testcase_08 AC 6 ms
11,672 KB
testcase_09 AC 7 ms
12,036 KB
testcase_10 AC 6 ms
11,648 KB
testcase_11 AC 97 ms
52,712 KB
testcase_12 AC 10 ms
11,648 KB
testcase_13 AC 10 ms
11,776 KB
testcase_14 AC 10 ms
11,648 KB
testcase_15 AC 670 ms
327,144 KB
testcase_16 AC 10 ms
11,776 KB
testcase_17 AC 9 ms
11,648 KB
testcase_18 AC 9 ms
11,776 KB
testcase_19 AC 503 ms
273,640 KB
testcase_20 AC 10 ms
11,776 KB
testcase_21 AC 10 ms
11,648 KB
testcase_22 AC 9 ms
11,648 KB
testcase_23 AC 10 ms
11,776 KB
testcase_24 AC 9 ms
11,648 KB
testcase_25 AC 9 ms
11,648 KB
testcase_26 AC 142 ms
68,940 KB
testcase_27 AC 681 ms
327,148 KB
testcase_28 AC 181 ms
87,784 KB
testcase_29 AC 57 ms
32,544 KB
testcase_30 AC 168 ms
86,116 KB
testcase_31 AC 343 ms
170,092 KB
testcase_32 AC 82 ms
43,756 KB
testcase_33 AC 58 ms
32,488 KB
testcase_34 AC 593 ms
327,272 KB
testcase_35 AC 46 ms
31,208 KB
testcase_36 AC 47 ms
31,208 KB
testcase_37 AC 25 ms
20,196 KB
testcase_38 AC 91 ms
52,712 KB
testcase_39 AC 165 ms
85,996 KB
testcase_40 AC 146 ms
86,108 KB
testcase_41 AC 91 ms
52,840 KB
testcase_42 AC 161 ms
87,656 KB
testcase_43 AC 25 ms
20,068 KB
testcase_44 AC 71 ms
41,192 KB
testcase_45 AC 435 ms
273,512 KB
testcase_46 AC 68 ms
40,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cstdint>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define fore(i, a) for(auto &&i : a)
#define foreP(a, b, v) for(auto &&[a, b] : v)
#define foreP3(a, b, c, v) for(auto &&[a, b, c] : v)
#define fitr(itr, m) for(auto &&itr=m.begin();itr!=m.end();itr++)
#define ALL(v) (v).begin(),(v).end()
#define SUM(a) accumulate(ALL(a),0LL)
#define VC vector
#define TP tuple

using namespace std;
mt19937 engine(time(0));

using ll = long long;
using ld = long double;
constexpr long long mod = 998244353;
// constexpr long long mod = 1000000007;
// constexpr long long mod = 100000000000000003;
constexpr double PI=3.1415926535897932384626433832795028841971;
constexpr long long inf = INT_MAX;
constexpr long long infll = LONG_MAX;

int dx[8] = {1, 0,-1, 0, 1, 1,-1,-1};
int dy[8] = {0, 1, 0,-1, 1,-1, 1,-1 };

using Si =set<int>;using Sll =set<long long>;using Sc =set<char>;using Ss =set<string>;
using Mii = map<int,int>;using Msi = map<string,int>;using Mci = map<char,int>;using Mlli = map<long long,int>;
using P = pair<int, int>;using PL = pair<long long, long long>;
using V = vector<int>;using VL = vector<long long>;using Vc = vector<char>;using Vs = vector<string>;
using VP = vector<P>;using VPL = vector<P>;
using VV = vector<vector<int>>;using VVL = vector<vector<long long>>;
using VVc = vector<vector<char>>;using VVs = vector<vector<string>>;
using VVP = vector<vector<P>>;using VVPL = vector<vector<PL>>;
using VVV = vector<vector<vector<int>>>;using VVVL = vector<vector<vector<ll>>>;using VVVP = vector<vector<vector<P>>>;

template<class T,class S>bool chmin(T& a, S b) {if(a<=b)return false;a = b;return true;};
template<class T,class S>bool chmax(T& a, S b) {if(a>=b)return false;a = b;return true;};

ll modpow(ll x, ll n, ll m = mod) {
    if (n < 0) {ll res = modpow(x, -n, m);return modpow(res, m - 2, m);}
	if (abs(x) >= m)x %= m;if (x < 0)x += m;//if (x == 0)return 0;
	ll res = 1;
	while (n) {if (n & 1)res = res * x % m;x = x * x % m; n >>= 1;}
	return res;
}

class modint {
public:
    int val;
    modint() :val(0) {}
    template<typename T>modint(T x=0): val(x%mod){if(val<0)val+=mod;}
    modint(const modint &r){val=r.val;}
    modint& operator=(const modint& other) {val = other.val;return *this;}
    modint& operator=(const int& other) {val = other;return *this;}
    modint& operator=(const long long& other) {val = other;return *this;}
    //算術演算子
    modint operator +(){return (*this);} //単項
    modint operator -(){return (val%mod+mod)%mod;} //単項
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    modint operator %(const modint &r){return modint(*this)%=r;}
    modint operator ^(long long r){modint ans = 1, x = val;while (r > 0) {if (r & 1) ans *= x;x *= x;r >>= 1;}return ans;}
    modint operator ++(int){val+=1;val%=mod; return *this;}
    modint operator --(int){(val==0)?val=mod-1:val-=1; return *this;}
    //代入演算子
    modint &operator +=(const modint &r){val+=r.val;if(val>=mod)val-=mod;return *this;}
    modint &operator -=(const modint &r){if(val<r.val)val+=mod;val-=r.val;return *this;}
    modint &operator *=(const modint &r){val=(ll)val*r.val%mod;return *this;}
    modint &operator /=(const modint &r){ll a=r.val,b=mod,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}val=val*u%mod;if(val<0)val+=mod;return *this;}
    modint &operator %=(const modint &r){val=val%r.val; return *this;}
    modint &operator ^=(const long long &r){(*this)=(*this)^r; return (*this);}
    //等価比較演算子
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator >(const modint& r){return this->val>r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
    // 他のクラスとの計算
    template <typename T>friend modint operator+(T t, const modint& o) {return modint(t) + o;}
    template <typename T>friend modint operator-(T t, const modint& o) {return modint(t) - o;}
    template <typename T>friend modint operator*(T t, const modint& o) {return modint(t) * o;}
    template <typename T>friend modint operator/(T t, const modint& o) {return modint(t) / o;}
};
istream &operator >>(istream &is,modint& x){ long long t; is >> t; x=modint(t); return is;}
ostream &operator <<(ostream &os,const modint& x){return os<<x.val;}

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = (1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * (i + 1);
	}
	factinv[max_n - 1] = (1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] *(i + 1);
	}
}

modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[a - b];
}

template<typename T>
T gcd(T a, T b) {
	a = abs(a); b = abs(b);
	if (a < b)swap(a, b);
	while(b){ll r = a % b; a = b; b = r;}
	return a;
}

template <class T,class S> istream &operator>>(istream &is, pair<T,S> &pir) {is >> pir.first >> pir.second; return is;}
template <class T> istream &operator>>(istream &is, vector<T> &vec) {for(T &i: vec) is >> i; return is;}
template <class... T> istream &operator>>(istream &is, tuple<T...> &tpl) {apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);return is;}

template <class OStream, class T> OStream &operator<<(OStream &os, const vector<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; itr++;if(itr!=vec.end())os <<" ";}return os;}
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const array<T, sz> &arr) {auto itr = arr.begin();while (itr != arr.end()){os << *itr; itr++;if(itr!=arr.end())os <<" ";}return os;}
template <class OStream, class... T> OStream &operator<<(OStream &os, const tuple<T...> &tpl) {apply([&os](auto &&...args) {int count = 0;((os << args << (++count != sizeof...(args) ? " " : "")), ...);}, tpl);return os;}
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa) {return os  << pa.first << ' ' << pa.second;}
template <class OStream, class T> OStream &operator<<(OStream &os, const set<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; itr++;if(itr!=vec.end())os <<" ";}return os;}

template <class OStream, class T> OStream &operator<<(OStream &os, const deque<T> &vec) {os << "deq[";for (auto v : vec) os << v << ',';os << ']';return os;}
template <class OStream, class T> OStream &operator<<(OStream &os, const queue<T> &vec) {os << "que[";for (auto v : vec) os << v << ',';os << ']';return os;}
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const map<TK, TV> &mp) {os << '{';for (auto v : mp) os << v.first << "=>" << v.second << ','<< endl;os << '}';return os;}
template<typename T>void out(T a){ cout << a << endl;}
template<typename T,typename S>void out(T a,S b){ cout << a <<" " << b << endl;}
template<typename T,typename S,typename U>void out(T a,S b,U c){ cout << a <<" " << b <<" " << c << endl;}
void yes(bool f=1,string yes="Yes",string no="No"){if(f){cout << yes << endl;}else{cout << no << endl;}}

template <class T>
void dfs_combination(vector<T> &arr, int idx, int r, vector<T> &pattern, vector<vector<T>> &result) {
    if (r == 0) {
        result.push_back(pattern);
        return;
    }
    if ((idx + r) > arr.size()) {
        return;
    }

    // select
    pattern.push_back(arr[idx]);
    dfs_combination(arr, idx + 1, r - 1, pattern, result);
    pattern.pop_back();
    // not select
    dfs_combination(arr, idx + 1, r, pattern, result);
}
template <class T>
vector<vector<T>> combination(vector<T> &arr, int r) {
    if (arr.size() < r) {
        printf("combination ERROR: r is larger than arr.size()\n");
        exit(1);
    }

    vector<T> pattern;
    vector<vector<T>> result;
    dfs_combination(arr, 0, r, pattern, result);
    return result;
}
void solve(){
    int N,K;
    cin >> N >> K ;
    VL A(N);
    cin >> A;
    sort(ALL(A));
    int ans = 0;
    for(VL i: combination(A,K)){
        ll a = 0;
        for(ll j:i){
            a += j;
        }
        if(a%998>=a%998244353){
            ans++;
        }
    }
    out(ans % 998);
    return;
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<setprecision(20);
    int t=1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}
0