#549097 (C++17) No.1238 選抜クラス

提出ソース

結果

問題	No.1238 選抜クラス
ユーザー	piddy
提出日時	2020-09-06 15:18:06
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	16 ms / 2,000 ms
コード長	5,540 bytes
コンパイル時間	999 ms
コンパイル使用メモリ	81,232 KB
実行使用メモリ	19,328 KB
最終ジャッジ日時	2024-05-06 23:33:56
合計ジャッジ時間	2,023 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	3 ms 5,376 KB
testcase_08	AC	3 ms 5,376 KB
testcase_09	AC	3 ms 5,632 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	3 ms 5,632 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	3 ms 5,632 KB
testcase_16	AC	3 ms 5,504 KB
testcase_17	AC	16 ms 19,328 KB
testcase_18	AC	14 ms 18,944 KB
testcase_19	AC	15 ms 19,200 KB
testcase_20	AC	14 ms 18,560 KB
testcase_21	AC	13 ms 18,048 KB
testcase_22	AC	15 ms 19,328 KB
testcase_23	AC	15 ms 19,328 KB
testcase_24	AC	15 ms 19,328 KB
testcase_25	AC	16 ms 19,328 KB
testcase_26	AC	14 ms 19,328 KB
testcase_27	AC	15 ms 19,328 KB
testcase_28	AC	15 ms 19,328 KB
testcase_29	AC	14 ms 19,072 KB
testcase_30	AC	5 ms 8,192 KB
testcase_31	AC	8 ms 12,160 KB
testcase_32	AC	11 ms 15,744 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	11 ms 17,024 KB
testcase_35	AC	6 ms 9,472 KB
testcase_36	AC	4 ms 6,400 KB
testcase_37	AC	5 ms 8,448 KB
testcase_38	AC	14 ms 18,560 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;

template<long long P>
long long modinv(long long n) {
	long long a = P, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a;
		std::swap(n, a);
		u -= t * v;
		std::swap(u, v);
	}
	u %= P;
	if (u < 0) u += P;
	return u;
}

template<long long M>
struct modint {
	long long val;

	modint<M>(long long right) : val(right) {sub(val);}
	modint<M>() {val = 0;}

	void sub(long long &n) {
		if (n < 0) {
			long long m = (-n) % M;
			n = M - m;
		}
		else n %= M;
	}

	modint<M> operator+ (modint<M> right) {return (this -> val) + right.val;}
	modint<M> operator+ (long long right) {sub(right); return (this -> val) + right;}
	modint<M> operator- (modint<M> right) {return (this -> val) - right.val;}
	modint<M> operator- (long long right) {sub(right); return (this -> val) - right;}
	modint<M> operator* (modint<M> right) {return (this -> val) * right.val;}
	modint<M> operator* (long long right) {sub(right); return (this -> val) * right;}

	bool operator== (modint<M> right) {return ((this -> val) == right.val);}
	bool operator== (long long right) {sub(right); return ((this -> val) == right);}
	bool operator!= (modint<M> right) {return ((this -> val) != right.val);}
	bool operator!= (long long right) {sub(right); return ((this -> val) != right);}
	bool operator<= (modint<M> right) {return ((this -> val) <= right.val);}
	bool operator<= (long long right) {sub(right); return ((this -> val) <= right);}
	bool operator>= (modint<M> right) {return ((this -> val) >= right.val);}
	bool operator>= (long long right) {sub(right); return ((this -> val) >= right);}
	bool operator< (modint<M> right) {return ((this -> val) < right.val);}
	bool operator< (long long right) {sub(right); return ((this -> val) < right);}
	bool operator> (modint<M> right) {return ((this -> val) > right.val);}
	bool operator> (long long right) {sub(right); return ((this -> val) > right);}

	void operator+= (modint<M> right) {*this = *this + right;}
	void operator+= (long long right) {*this = *this + right;}
	void operator-= (modint<M> right) {*this = *this - right;}
	void operator-= (long long right) {*this = *this - right;}
	void operator*= (modint<M> right) {*this = *this * right;}
	void operator*= (long long right) {*this = *this * right;}

	modint<M>& operator++ () {*this += 1; return *this;}
	modint<M> operator++ (int) {*this += 1; return *this - 1;}
	modint<M>& operator-- () {*this -= 1; return *this;}
	modint<M> operator-- (int) {*this -= 1; return *this + 1;}

	modint<M> operator/ (modint<M> right) {return *this * modinv<M>(right.val);}
	modint<M> operator/ (long long right) {sub(right); return *this * modinv<M>(right);}

	void operator/= (modint<M> right) {*this = *this / right;}
	void operator/= (long long right) {*this = *this / right;}
};

std::vector<long long> factorial;
std::vector<long long> factorial_inv;

template<long long P>
void make_table(long long n) {
	factorial.resize(n + 1, 1); factorial_inv.resize(n + 1, 1);
	for (long long i = 2; i <= n; i++) {
		factorial[i] = factorial[i - 1] * i % P;
	}
	factorial_inv[n] = modinv<P>(factorial[n]);
	for (long long i = n - 1; i >= 0; i--) {
		factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % P;
	}
}

template<long long P>
modint<P> permutation(long long n, long long r) {
	if (n <= factorial.size()) {
		modint<P> a = factorial[n], b = factorial_inv[n - r];
		return a * b;
	}
	else {
		std::cerr << "attention : factorial table is not constructed" << '\n';
		modint<P> ret = 1;
		for (long long i = 0; i < r; i++) ret *= n - i;
		return ret;
	}
}

template<long long P>
modint<P> combination(long long n, long long r) {
	r = std::min(r, n - r);
	if (n <= factorial.size()) {
		return permutation<P>(n, r) * factorial_inv[r];
	}
	else {
		std::cerr << "attention : factorial table is not constructed" << '\n';
		modint<P> ret = 1;
		for (long long i = 0; i < r; i++) {
			ret *= n - i;
			ret /= i + 1;
		}
		return ret;
	}
}

template<long long M>
modint<M> modpow(long long a, long long n) {
	a %= M;
	if (n == 0) return 1;
	if (a == 0) return 0;
	if (a == 1) return 1;
	long long b = 1, cnt = 0;
	while (b < M && cnt < n) {
		b *= a;
		cnt++;
	}
	modint<M> ret;
	if (b < M) ret = b;
	else {
		b %= M;
		ret = modpow<M>(b, n / cnt) * modpow<M>(a, n % cnt);
	}
	return ret;
}

template<long long M>
modint<M> modpow(modint<M> m, long long n) {
	long long a = m.val;
	if (n == 0) return 1;
	if (a == 0) return 0;
	if (a == 1) return 1;
	long long b = 1, cnt = 0;
	while (b < M && cnt < n) {
		b *= a;
		cnt++;
	}
	modint<M> ret;
	if (b < M) ret = b;
	else {
		b %= M;
		ret = modpow<M>(b, n / cnt) * modpow<M>(a, n % cnt);
	}
	return ret;
}

template<long long M>
std::ostream &operator<< (std::ostream &out, modint<M> tgt) {out << tgt.val; return out;}

int main() {
	int N, K;
	cin >> N >> K;
	assert(1 <= N && N <= 100 && 0 <= K && K <= 100);
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		assert(0 <= A[i] && A[i] <= 100);
	}

	for (int i = 0; i < N; i++) A[i] -= K;

	const int P = 1000000007;
	vector<vector<modint<P>>> dp(N, vector<modint<P>>(20001, 0));
	// dp[i][j] = A[i] まで見て和が j - 10000 になる部分列の個数
	dp[0][A[0] + 10000]++;
	for (int i = 1; i < N; i++) {
		dp[i] = dp[i - 1];
		dp[i][A[i] + 10000]++;
		for (int j = 0; j < 20001; j++) {
			if (dp[i - 1][j] > 0) dp[i][j + A[i]] += dp[i - 1][j];
		}
	}

	modint<P> ans = 0;
	for (int j = 10000; j < 20001; j++) ans += dp[N - 1][j];
	cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード