#779679 (C++17) No.1897 Sum of 2nd Max

提出ソース

結果

問題	No.1897 Sum of 2nd Max
ユーザー	re_re0101
提出日時	2022-07-19 17:53:00
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	116 ms / 2,000 ms
コード長	9,948 bytes
コンパイル時間	4,592 ms
コンパイル使用メモリ	274,652 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-01 21:14:05
合計ジャッジ時間	7,444 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	115 ms 6,940 KB
testcase_04	AC	112 ms 6,944 KB
testcase_05	AC	56 ms 6,940 KB
testcase_06	AC	62 ms 6,940 KB
testcase_07	AC	75 ms 6,944 KB
testcase_08	AC	59 ms 6,944 KB
testcase_09	AC	115 ms 6,944 KB
testcase_10	AC	115 ms 6,944 KB
testcase_11	AC	116 ms 6,940 KB
testcase_12	AC	115 ms 6,940 KB
testcase_13	AC	116 ms 6,940 KB
testcase_14	AC	42 ms 6,944 KB
testcase_15	AC	44 ms 6,940 KB
testcase_16	AC	56 ms 6,940 KB
testcase_17	AC	50 ms 6,944 KB
testcase_18	AC	53 ms 6,940 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	115 ms 6,940 KB
testcase_31	AC	116 ms 6,940 KB
testcase_32	AC	76 ms 6,940 KB
testcase_33	AC	116 ms 6,940 KB

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

ソースコード

raw source code

// #pragma GCC optimize ("O3")
// #pragma GCC target("avx512f")
// #pragma GCC optimize("unroll-loops")
// #ifndef ONLINE_JUDGE
// #define _GLIBCXX_DEBUG
// #endif
#include<bits/stdc++.h>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/rational.hpp>
// namespace mp = boost::multiprecision;
// using Bint=mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<64>>;
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#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 rrep(i, a, b) for(ll i = (b); i --> (a); )
int scan(){ return getchar(); }
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++) { int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T> void scan(deque<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); }
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...); }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define eb emplace_back
#define endl '\n'
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define pi 3.14159265359
const double eps = 1e-12;
const long long INF= (long long)2e18+20;
const int inf= 1010101010;
typedef long double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> Point;  // Point
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl>vvl;
typedef vector<vvl>vvvl;
typedef vector<vvvl>vvvvl;
typedef vector<vvvvl>vvvvvl;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<vvi>vvvi;
typedef vector<vvvi>vvvvi;
typedef vector<vvvvi>vvvvvi;
typedef pair<ll,ll> P;
#define __builtin_popcount __builtin_popcountll
// typedef double D;    
template<class T> using minpq=priority_queue<T,vector<T>,greater<T>>;
// const ll MOD=1000000007LL;
const ll MOD=998244353LL;
using mint=modint998244353;
// using mint=modint;
// using mint=modint1000000007;
// using mint=modint;
typedef vector<mint> vm;
typedef vector<vector<mint> >vvm;
typedef vector<vector<vector<mint> > >vvvm;
//上下右左
vl dx={-1,1,0,0,1,1,-1,-1};
vl dy={0,-0,1,-1,-1,1,-1,1};


template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
template<class T> ll sum(const T& a){ return accumulate(all(a), 0LL); }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 5000010;//5*10^6
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll 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;
    }
}

// 二項係数計算
long long COM(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;
}


//素数判定O(√n)
bool is_prime(ll n){
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return n!=1;
}

//約数の列挙O(√n)
vector<ll>divisor(ll n){
  vector<ll>res;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      res.push_back(i);
      if(i != n/i) res.push_back(n/i);
    }
  }
  return res;
}


ll exp(ll n,ll r){
    if(r==0)return 1;
    return n*exp(n,r-1);
}

ll factorial(int n){
    if(n==0)return 1;
    return n*factorial(n-1);
}

template< typename T >
struct Compress {
  vector< T > xs;

  Compress() = default;

  Compress(const vector< T > &vs) {
    add(vs);
  }

  Compress(const initializer_list< vector< T > > &vs) {
    for(auto &p : vs) add(p);
  }

  void add(const vector< T > &vs) {
    copy(begin(vs), end(vs), back_inserter(xs));
  }

  void add(const T &x) {
    xs.emplace_back(x);
  }

  void build() {
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
  }

  vector< int > get(const vector< T > &vs) const {
    vector< int > ret;
    transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
      return lower_bound(begin(xs), end(xs), x) - begin(xs);
    });
    return ret;
  }

  int get(const T &x) const {
    return lower_bound(begin(xs), end(xs), x) - begin(xs);
  }

  const T &operator[](int k) const {
    return xs[k];
  }
};


template<class T>
void rotate90(ll &h,ll &w,vector<vector<T>>&vec){
    vector<vector<T>>vec2(w,vector<T>(h));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            vec2[j][h-1-i]=vec[i][j];
        }
    }
    vec=vec2;
    swap(h,w);
}

struct RandomNumberGenerator {
  mt19937 mt;

  RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}

  int operator()(int a, int b) { // [a, b)
    uniform_int_distribution< int > dist(a, b - 1);
    return dist(mt);
  }

  int operator()(int b) { // [0, b)
    return (*this)(0, b);
  }
};


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    //主客転倒！二重和のときは一番内側の物が何回使われるか
    //√Nで分けるテク
    //絶対値は外して2通りの式にした後、変数ごとにまとめる
    //組み合わせが少ないそうなものはdfsで実行してみる（典型25）
    //DはDPのD
    //pow_mod,prime_factor,divisor,is_prime
    // g++ -fsanitize=undefined code.cpp -I.
    // valgrind ./a.out
    /*--------------------------------*/

    ll n,k;cin>>n>>k;
    mint ans1=0;
    for(ll i=1;i<=k;i++){
        ans1+=(mint)i*(pow_mod(i,n,MOD)-pow_mod(i-1,n,MOD)-(mint)n*pow_mod(i-1,n-1,MOD));
    }
    vm f(k);
    for(ll i=1;i<=k-1;i++){
        f[i]=(mint)n*i*(pow_mod(i,n-1,MOD)-pow_mod(i-1,n-1,MOD));
    }
    for(ll i=1;i<=k-1;i++)f[i]+=f[i-1];
    mint ans=ans1;
    for(ll i=1;i<=k-1;i++)ans+=f[i];
    cout<<ans.val()<<endl;


}

yukicoder

結果

テストケース

ソースコード