Submission #70636254

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
/* 降順 */
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a < b) - (a > b);
}
#define MOD_BY 1000000007
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int mul(int a, int b) {
  return (int)((long long)a * b % MOD_BY);
}
int N;
int C[212345];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

/* 降順 */
int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a < b) - (a > b);
}

#define MOD_BY 1000000007

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

int N;
int C[212345];

int twon[212345];

int main(void) {
	int i;
	int ans = 0;
	int mult = 1, num = 1;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &C[i]) != 1) return 1;
	}
	qsort(C, N, sizeof(*C), cmp);
	twon[0] = 1;
	for (i = 1; i <= N; i++) twon[i] = mul(twon[i - 1], 2);
	for (i = 0; i < N; i++) {
		ans = add(ans, mul(mul(C[i], mult), twon[N - i -1]));
		mult = add(mul(mult, 2), num);
		num = mul(num, 2);
	}
	printf("%d\n", mul(ans, twon[N]));
	return 0;
}

/*

自分より小さいのがある → それを先に

1：1個×1、2個(全部可)×2、3個(全部可)×1
2：1個×1、2個(1以外)×1
3：1個×1

パスカルの三角形 → 上からn段目の合計は2**nじゃね？

大きい方からn番目 → 2**n を掛ける

これは、Sを全部0に固定した場合
Sを変えていく → xorするだけで実質同じ
よって、2**Nを掛ければよい

↑大嘘？答えが合わない

1 2 のとき
1 → 1×1＝1
2 → 2×1＝2
1 2 → 1×2＋2×1＝4

1：1×1＋1×2 (1+2)
2：2×1＋2×1 (1+1)

たしかに、明らかにさっきの見積もりと違う

自分より大きいものの数 → 係数に加算される (※)
自分より小さいものの数 → 係数に加算されない (パターン数を増やすのみ)

※について
既に計算済みの部分に、1ビット追加することを考える
追加ビットが0 → 重み・パターン数ともに変わらない
追加ビットが1 → パターン数が同じで、重みが全て1ずつ増える
したがって
重み += 重み + パターン数
パターン数 *= 2

*/

Submission Info

Judge Result