結果
| 問題 |
No.1238 選抜クラス
|
| コンテスト | |
| ユーザー |
 piddy
|
| 提出日時 | 2020-09-06 08:01:16 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,540 bytes |
| コンパイル時間 | 2,333 ms |
| コンパイル使用メモリ | 88,752 KB |
| 最終ジャッジ日時 | 2025-01-14 07:26:31 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:26:19: error: expected unqualified-id before 'long'
26 | modint<M>(long long right) : val(right) {sub(val);}
| ^~~~
main.cpp:26:19: error: expected ')' before 'long'
26 | modint<M>(long long right) : val(right) {sub(val);}
| ~^~~~
| )
main.cpp:27:19: error: expected unqualified-id before ')' token
27 | modint<M>() {val = 0;}
| ^
main.cpp: In function 'int main()':
main.cpp:178:67: error: no matching function for call to 'std::vector<modint<1000000007> >::vector(int, int)'
178 | vector<vector<modint<P>>> dp(N, vector<modint<P>>(20001, 0));
| ^
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/vector:64,
from main.cpp:2:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_vector.h:704:9: note: candidate: 'template<class _InputIterator, class> constexpr std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with <template-parameter-2-2> = _InputIterator; _Tp = modint<1000000007>; _Alloc = std::allocator<modint<1000000007> >]'
704 | vector(_InputIterator __first, _InputIterator __last,
| ^~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_vector.h:704:9: note: template argument deduction/substitution failed:
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/stl_construct.h:61,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/bits/char_traits.h:46,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ios:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.4.0/include/c++/12/iostrea
ソースコード
#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;
}