結果
| 問題 | No.1238 選抜クラス |
| ユーザー |
 piddy
|
| 提出日時 | 2020-09-06 05:33:20 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,190 bytes |
| コンパイル時間 | 1,996 ms |
| コンパイル使用メモリ | 87,256 KB |
| 最終ジャッジ日時 | 2025-01-14 07:25:15 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:172:25: error: conversion from 'int' to non-scalar type 'modint<1000000007>' requested
172 | modint<P> ans = 0;
| ^
main.cpp: In instantiation of 'modint<M> modint<M>::operator-(long long int) [with long long int M = 1000000007]':
main.cpp:65:55: required from 'modint<M> modint<M>::operator++(int) [with long long int M = 1000000007]'
main.cpp:179:44: required from here
main.cpp:40:81: error: could not convert '(((modint<1000000007>*)this)->modint<1000000007>::val - right)' from 'long long int' to 'modint<1000000007>'
40 | modint<M> operator- (long long right) {sub(right); return (this -> val) - right;}
| ~~~~~~~~~~~~~~^~~~~~~
| |
| long long int
main.cpp: In instantiation of 'modint<M> modint<M>::operator+(long long int) [with long long int M = 1000000007]':
main.cpp:58:51: required from 'void modint<M>::operator+=(long long int) [with long long int M = 1000000007]'
main.cpp:65:36: required from 'modint<M> modint<M>::operator++(int) [with long long int M = 1000000007]'
main.cpp:179:44: required from here
main.cpp:38:81: error: could not convert '(((modint<1000000007>*)this)->modint<1000000007>::val + right)' from 'long long int' to 'modint<1000000007>'
38 |
ソースコード
#include <iostream>
#include <vector>
#include <bitset>
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;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
const int P = 1000000007;
modint<P> ans = 0;
for (int i = 1; i < (1 << N); i++) {
bitset<32> bs = i;
int sum = 0;
for (int j = 0; j < N; j++) {
if (bs[j]) sum += A[j];
}
if (sum >= K * __builtin_popcount(i)) ans++;
}
cout << ans << endl;
}