Submission #21365226

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(ll i = 0; i<n; i++)
#define rep_s(i, start, n) for(ll i= start;  i<n; i++)
#define rep_down(i, n) for(ll i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(ll i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()
//int count = 0; // 組合せの総数
ll ans = 614889782588491412;
ll array_prime[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
ll x[60];
// 実際に組合せを生成する
// comb: 生成された組合せ配列
// step: n桁目までが生成されていることを示す。
// init: その桁始まりの数を示す。
void makeCombination(vector<ll> comb, int n, int r, int step, int init, ll N_){
 // r桁すべてが生成された
     
     if(step == r){
        ll tmp = 1, tmp2;
        for (int j = 0; j < r; ++j){
           	 tmp2 = array_prime[comb[j]];
             tmp *= tmp2;
             //cout << "comb[j]: " << comb[j] << endl;
        }
        //cout << tmp << endl;
        rep(k, N_)
        {
          if (gcd(x[k], tmp) == 1)
            break;
          if (k == N_ - 1)
            ans = min(ans, tmp);
        }
        //cout << ans << endl;
          
        //cout << endl;
        //count++;
         return;
     }

     // 全桁生成されていない
    for (int i = init; i <= n-r+step; ++i){
        comb.push_back(i);
        makeCombination(comb, n, r, step+1, i+1, N_);
        // ここで配列から一つ排除しないと困ったことになる
        comb.pop_back();
    }
}

// makeCombinationに値を渡すためだけの関数
// n個の中からr個選択する
void combination(int n, int r, ll N_){
     vector<ll> comb;
     makeCombination(comb, n, r, 0, 0, N_);
}

/*
60
1 2 3 4 5 6 10 12 15 20 30 60
odd: 4
even: 8

36
1 2 3 4 6 9 12 18 36
odd: 3
even: 6

4 * 3 * 3 * 3
420

*/


int main(void) {
  /*
  ll N;
  cin >> N;
  ll a[N];
  rep(i, N) cin >> a[i];
  
  if (N == 1)
  {
    cout << a[0] * a[0] %  998244353 << endl;
    return 0;
  }
  ll sum = 0;
  rep(i, N)
  {
    sum += a[i] %  998244353;
    sum %= 998244353;
  }
  ll n_2 = 1;
  rep(i, N)
  {
    n_2 *= 2;
    n_2 %= 998244353;
    cout << n_2 << endl;
  }
  cout << n_2 << endl;
  n_2--;
  cout << sum << " " << n_2 << endl;
  ll ans = n_2 * sum;
  ans %= 998244353;
  cout << ans << endl;
  */
  ll N;
  cin >> N;
  vector<ll> a(N);
  rep(i, N) cin >> a[i];
  ll ans = 0;
  sort(ALL(a));
  reverse(ALL(a));
  /*
  if (N == 1)
  {
    cout << a[0] * a[0] %  998244353 << endl;
    return 0;
  }
  */
  //ll sum[N];
  //sum[0] = a[0];
  //rep(i, N - 1) sum[i + 1] += sum[i] + a[i + 1];
  ll sum = a[0];
  //cout << sum << " " << sum * a[0] << endl;
  ans = sum * a[0] % 998244353;
  
  //cout << ans << endl;
  rep(i, N - 1)
  {
    sum += 998244353;
    sum = sum * 2 + (a[i + 1] - a[i]);
    sum %= 998244353;
    /*
    if (i == N - 2) sum %= 998244353;
    else
    {
      if (a[i + 1] - a[ i + 2] < (sum % 998244353) * 2) sum %= 998244353;
     }
     */
    ans += (sum * a[i + 1]) % 998244353;
    ans %= 998244353;
    //cout << ans << " " << sum << " " << sum * a[i] << endl;
  }
  //ll dfa = 1996488706 * 998244353;
  //cout << dfa << endl;
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result