fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define all(v)        ((v).begin()), ((v).end())
  6. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  7. #define pb            push_back
  8. #define ppb           pop_back
  9. #define F             first
  10. #define S             second
  11. #define B             begin()
  12. #define E             end()
  13. #define clr(x)        memset(x,0,sizeof(x))
  14. #define endl          '\n'
  15. #define coutfloat(n,d)     cout << fixed << setprecision(d) << n << endl
  16. #define FASTIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  17.  
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double   ld;
  22. typedef pair<int, int> pi;
  23. typedef vector<bool>      vb;
  24. typedef vector<vb>        vvb;
  25. typedef vector<string>    vs;
  26. typedef vector<int>       vi;
  27. typedef vector<ll>       vll;
  28. typedef vector<double>    vd;
  29. typedef vector< vi >      vvi;
  30.  
  31.  
  32. #ifndef ONLINE_JUDGE
  33. #define deb(x) cerr << #x <<" "; _print(x); cerr << endl;
  34. #else
  35. #define deb(x)
  36. #endif
  37.  
  38. void _print(ll t) {cerr << t;}
  39. void _print(int t) {cerr << t;}
  40. void _print(string t) {cerr << t;}
  41. void _print(char t) {cerr << t;}
  42. void _print(ld t) {cerr << t;}
  43. void _print(double t) {cerr << t;}
  44. void _print(ull t) {cerr << t;}
  45.  
  46. template <class T, class V> void _print(pair <T, V> p);
  47. template <class T> void _print(vector <T> v);
  48. template <class T> void _print(set <T> v);
  49. template <class T, class V> void _print(map <T, V> v);
  50. template <class T> void _print(multiset <T> v);
  51. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}";}
  52. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  53. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  54. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  55. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  56.  
  57. const int dx[] = {0,0,1,-1};
  58. const int dy[] = {1,-1,0,0};
  59.  
  60. const ll inf = 1e9+1000;
  61. const double eps = (1e-8);
  62. const ll mod = 998244353;
  63.  
  64. const int N = 3e5, M = 10;
  65. int k,n,m;
  66.  
  67. ll mpow(ll bs, ll exp) {
  68.     ll res = 1;
  69.     bs = bs % mod;
  70.     while (exp > 0) {
  71.         if (exp & 1)
  72.             res = (res * bs) % mod;
  73.         exp = exp >> 1;
  74.         bs = (bs * bs) % mod;
  75.     }
  76.     return res;
  77. }
  78. ll fact[N] , fact_inv[N];
  79. inline ll nck(ll n,ll k){    
  80.     if(n<0 || k>n) return 0;
  81.     return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
  82. }
  83. void cf(){
  84.     fact[0] = 1;
  85.     for(ll i = 1;i < N;i++) fact[i] = i * fact[i - 1] % mod;
  86.     fact_inv[N - 1] = mpow(fact[N - 1] , mod - 2);
  87.     for(ll i = N - 2;i >= 0;i--) fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod;
  88. }
  89. //! don't forget to call cf()
  90.  
  91.  
  92. void solve(){
  93.     cin>>n;
  94.     vll a(n); rep(i,0,n) cin>>a[i];
  95.     sort(all(a));
  96.     ll ans = 0;
  97.     for(int choose = 1; choose<=n; choose++){
  98.         for(int ind = choose; ind<=n; ind++){
  99.             ans += a[ind-1] * nck(ind-1, choose-1);
  100.             ans%=mod;
  101.         }
  102.     }
  103.     cout<<ans<<endl;
  104. } 
  105.  
  106. int main(){
  107.     FASTIO;
  108.     cf();
  109.     int t= 1;
  110.     // cin>>t;
  111.     while(t--) solve();
  112.  
  113.  
  114.     return 0;
  115. }
Success #stdin #stdout 0.01s 8272KB
comments (?)
stdin
copy 
4
1 3 3 7
stdout
copy 
75
https://ideone.com/LCWUzK
language:
C++ (gcc 8.3)
created:
47 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!