ARC096

https://beta.atcoder.jp/contests/arc096

C.
Cを全通り試します。

ll A, B, C, X, Y;

void solve() {
	cin >> A >> B >> C >> X >> Y;
	ll ans = linf;
	for(int c = 0; c <= max(X, Y) * 2; c += 2) {
		ll res = 0;
		res += C * c;
		res += A * max(X - c / 2, 0ll);
		res += B * max(Y - c / 2, 0ll);
		MIN(ans, res);
	}
	cout << ans << "\n";
}

D.
折り返す場所を全通り試します。

int N; ll C;
ll X[MAX_N], V[MAX_N];
ll L1[MAX_N], L2[MAX_N], R1[MAX_N], R2[MAX_N];

void solve() {
	cin >> N >> C;
	rep(i, 0, N) {
		cin >> X[i] >> V[i];
	}

	ll vs = 0, l1m = 0, l2m = 0;
	rep(i, 0, N) {
		vs += V[i];
		MAX(l1m, vs - X[i]);
		MAX(l2m, vs - 2 * X[i]);
		L1[i + 1] = l1m;
		L2[i + 1] = l2m;
	}
	vs = 0; ll r1m = 0, r2m = 0;
	rer(i, N, 0) {
		vs += V[i];
		MAX(r1m, vs - (C - X[i]));
		MAX(r2m, vs - 2 * (C - X[i]));
		R1[i] = r1m;
		R2[i] = r2m;
	}
	ll res = 0;
	rep(i, 0, N + 1) {
		MAX(res, L1[i] + R2[i]);
		MAX(res, L2[i] + R1[i]);
	}
	cout << res << "\n";
}

E.
うわー2byte差で落とすというね…。
包除原理します。
そして、dp[i][j]:=iケタ0or1にするときその中で1を含む数の個数がjの時の場合の数とします。
するとdp[i][j]は簡単な遷移で求められて、
あとはiケタ0or1にするときの場合の数は、
ΣC(N,i)*2^(2^(N-i))*2^((N-i)*j)*dp(i,j)となるのでO(N^2)で求められます。
しかし、注意すべきことはpow(2,pow(2,N-i,mod),mod)としないことです。正しくは
pow(2,pow(2,N-i,mod-1),mod)です。2^(p-1)=1だからですね。これさえ気づければ通っていた…。

ll dp[3010][3010];

void solve() {
	cin >> N >> mod;
	C_init(N + 10);

	dp[0][0] = 1;
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(dp[i][j] == 0) continue;
			ADD(dp[i + 1][j + 1], dp[i][j]);
			ADD(dp[i + 1][j], dp[i][j] * (j + 1) % mod);
		}
	}
	ll ans = 0;
	rep(i, 0, N + 1) {
		ll dps = 0;
		ll pown = mod_pow(2, mod_pow(2, N - i, mod - 1), mod);
		ll pp = mod_pow(2, N - i, mod);
		ll d = 1;
		rep(j, 0, i + 1) {
			ll pows = pown * d % mod;
			MUL(d, pp);
			ADD(dps, dp[i][j] * pows % mod);
		}
		if(i % 2 == 0) {
			ADD(ans, (C(N, i) * dps % mod));
		}
		else {
			ADD(ans, mod - (C(N, i) * dps % mod));
		}
	}
	cout << ans << "\n";
}

mod-1の件があったにせよ、解法を詰めるのが遅すぎですね…場合の数の計算に自信が持てないのはなんとかしないと…。