結果
問題 | No.1238 選抜クラス |
ユーザー | sapphire__15 |
提出日時 | 2020-09-26 02:42:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 5,526 bytes |
コンパイル時間 | 1,130 ms |
コンパイル使用メモリ | 113,432 KB |
実行使用メモリ | 19,648 KB |
最終ジャッジ日時 | 2023-09-10 20:10:28 |
合計ジャッジ時間 | 3,413 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
4,376 KB |
testcase_01 | AC | 3 ms
4,376 KB |
testcase_02 | AC | 6 ms
5,056 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 4 ms
4,424 KB |
testcase_08 | AC | 5 ms
4,796 KB |
testcase_09 | AC | 7 ms
5,660 KB |
testcase_10 | AC | 4 ms
4,624 KB |
testcase_11 | AC | 7 ms
5,392 KB |
testcase_12 | AC | 5 ms
4,976 KB |
testcase_13 | AC | 5 ms
5,016 KB |
testcase_14 | AC | 5 ms
4,836 KB |
testcase_15 | AC | 6 ms
5,976 KB |
testcase_16 | AC | 6 ms
5,404 KB |
testcase_17 | AC | 35 ms
19,592 KB |
testcase_18 | AC | 34 ms
18,896 KB |
testcase_19 | AC | 33 ms
18,920 KB |
testcase_20 | AC | 33 ms
18,976 KB |
testcase_21 | AC | 32 ms
18,004 KB |
testcase_22 | AC | 36 ms
19,648 KB |
testcase_23 | AC | 33 ms
19,052 KB |
testcase_24 | AC | 35 ms
19,596 KB |
testcase_25 | AC | 36 ms
19,528 KB |
testcase_26 | AC | 35 ms
19,504 KB |
testcase_27 | AC | 34 ms
19,332 KB |
testcase_28 | AC | 34 ms
19,560 KB |
testcase_29 | AC | 33 ms
18,972 KB |
testcase_30 | AC | 12 ms
8,292 KB |
testcase_31 | AC | 20 ms
12,300 KB |
testcase_32 | AC | 26 ms
15,760 KB |
testcase_33 | AC | 4 ms
4,528 KB |
testcase_34 | AC | 30 ms
17,104 KB |
testcase_35 | AC | 14 ms
9,360 KB |
testcase_36 | AC | 8 ms
6,548 KB |
testcase_37 | AC | 12 ms
8,788 KB |
testcase_38 | AC | 33 ms
18,624 KB |
ソースコード
// #include "pch.h" #include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <bitset> #include <climits> #include <string> #include <cmath> #include <bitset> #include <complex> #include <functional> #include <ctime> #include <cassert> #include <fstream> #include <stack> #include <random> typedef long long ll; typedef std::pair<int, int> Pii; typedef std::pair<long long, long long> Pll; typedef std::pair<double, double> Pdd; #define rip(i, n, s) for (int i = (s);i < (int)( n ); i++) #define all(a) a.begin(), a.end() #define MM << " " << template<typename T> using MaxHeap = std::priority_queue<T>; template<typename T> using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>; template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<typename T> void vdeb(std::vector<T> &bb) { for (int i = 0;i < bb.size();i++) { if (i == bb.size() - 1) std::cout << bb[i]; else std::cout << bb[i] << ' '; } std::cout << '\n'; } template<typename T> void vdeb(std::vector<std::vector<T>> &bb) { for (int i = 0;i < bb.size();i++) { std::cout << i << ' '; vdeb(bb[i]); } std::cout << '\n'; } long long pow(long long n, long long p, long long k) {//n^k(mod p) if (!k) return 1; long long a = pow(n,p, k>>1); a = a * a%p; if (k & 1) a = a * n%p; return a; } void euclid(long long &a, long long &b, long long p) { // a>=b A*b+B*(a-a/b*b)=1 if (a == 1) { a = 1; } else { long long A = b, B = a % b; euclid(A, B, p); b = (A - (p + a / b) % p * B % p + p) % p; a = B; } } long long rev(long long n, long long p) {// n*x-p*y=1 //long long q = p; //euclid(p, n, p); //return n % q; return pow(n,p,p-2); } long long bino(long long n, long long m, long long p) {//nCm(mod p) long long ans = 1, div = 1; for(int i = 0;i < m; i++){ ans = (n - i) * ans % p; div = div * (i +1) % p; } return ans * rev(div, p) % p; } struct modint { long long num; long long p; modint() { num = 0; p = 1000000007; } modint(long long x) { p = 1000000007; num = x % p; } modint inv()const{return rev(num, p);} modint operator-() const{return modint(p-num);} modint& operator+=(const modint &other){ num = (num + other.num) % p; return *this; } modint& operator-=(const modint &other){ num = (num - other.num + p) % p; return *this; } modint& operator*=(const modint &other){ num = (num * other.num) % p; return *this; } modint& operator/=(const modint &other){ (*this) *= other.inv(); return *this; } modint& operator+=(const long long &other){ num = (num + other) % p; return *this; } modint& operator-=(const long long &other){ num = (num - other + p) % p; return *this; } modint& operator*=(const long long &other){ num = (num * other) % p; return *this; } modint& operator/=(const long long &other){ (*this) *= rev(other, p); return *this; } modint& operator++(){return *this += 1;} modint& operator--(){return *this -= 1;} modint& operator=(const long long &other){return (*this) = modint(other);} modint operator+(const modint &other) const{return modint(*this) += other;} modint operator-(const modint &other) const{return modint(*this) -= other;} modint operator*(const modint &other) const{return modint(*this) *= other;} modint operator/(const modint &other) const{return modint(*this) /= other;} modint operator+(const long long &other) const{return modint(*this) += other;} modint operator-(const long long &other) const{return modint(*this) -= other;} modint operator*(const long long &other) const{return modint(*this) *= other;} modint operator/(const long long &other) const{return modint(*this) /= other;} bool operator==(const modint &other) const{return num == other.num;} }; std::istream& operator>>(std::istream &is, const modint x) { std::cin >> x.num; return is; } std::ostream& operator<<(std::ostream &os, const modint &x){ std::cout << x.num; return os; } using namespace std; int main() { int n, k; cin >> n >> k; vector<int> da(n); rip(i,n,0) cin >> da[i]; rip(i,n,0) da[i] -= k; vector<int> da1(0), da2(0); rip(i,n,0) { if(da[i] >= 0) da1.push_back(da[i]); else da2.push_back(-da[i]); } vector<vector<modint>> pos(da1.size()+1, vector<modint>(10100)); vector<vector<modint>> neg(da2.size()+1, vector<modint>(10100)); pos[0][0] += 1; rip(i,da1.size(), 0) { rip(j, 10000, 0) { pos[i+1][j] += pos[i][j]; if(j+da1[i] <= 10000) { pos[i+1][j+da1[i]] += pos[i][j]; } } } neg[0][0] += 1; rip(i,da2.size(), 0) { rip(j, 10000, 0) { neg[i+1][j] += neg[i][j]; if(j+da2[i] <= 10000) { neg[i+1][j+da2[i]] += neg[i][j]; } } } modint now, ans; rip(i,10001,0) { now += neg.back()[i]; ans += pos.back()[i] * now; } cout << ans-1 << endl; }