結果
問題 | No.8046 yukicoderの過去問 |
ユーザー | Gosu_Hiroo |
提出日時 | 2020-08-03 21:52:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 12,369 bytes |
コンパイル時間 | 2,812 ms |
コンパイル使用メモリ | 220,388 KB |
実行使用メモリ | 36,924 KB |
最終ジャッジ日時 | 2024-09-13 17:33:30 |
合計ジャッジ時間 | 5,337 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 150 ms
36,400 KB |
testcase_01 | AC | 150 ms
36,536 KB |
testcase_02 | AC | 151 ms
36,432 KB |
testcase_03 | AC | 153 ms
36,404 KB |
testcase_04 | AC | 150 ms
36,404 KB |
testcase_05 | AC | 153 ms
36,408 KB |
testcase_06 | AC | 161 ms
36,772 KB |
testcase_07 | AC | 155 ms
36,732 KB |
testcase_08 | AC | 159 ms
36,924 KB |
ソースコード
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ #include <bits/stdc++.h> using namespace std; using ll = long long; #pragma GCC optimize("O3") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast") #define VI vector<int> #define G(size_1) vector<vector<int>>(size_1, vector<int>()) #define SZ(x) ((int)(x).size()) #define READ ({int t;cin >> t;t;}) #define PII pair<int, int> #define FOR(i, _begin, _end) for (__typeof(_end) end = _end, begin = _begin, i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define REP(i, end) for (__typeof(end) i = 0, _len = (end); i < (_len); i += 1) #define ALL(x) (x).begin(),(x).end() #define RALL(x) (x).rbegin(),(x).rend() #define F first #define S second #define y0 y3487465 #define y1 y8687969 #define j0 j1347829 #define j1 j234892 #define BIT(n) (1LL<<(n)) #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); #define EB emplace_back #define PB push_back #define fcout cout << fixed << setprecision(12) #define fcerr cerr << fixed << setprecision(12) #define print(x) cout << (x) << '\n' #define printE(x) cout << (x) << endl #define fprint(x) cout << fixed << setprecision(12) << (x) << endl # define BYE(a) do { cout << (a) << endl; return ; } while (false) #ifdef DEBUG #define DBG(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(cerr,_it, args); } #define ERR(x) std::cerr << #x << " = " << x << endl; #else #define DBG(x) {}; #define ERR(args...) {}; #endif void _err(std::ostream& cerr,istream_iterator<string> it) {cerr << endl;} template<typename T, typename... Args> void _err(std::ostream& cerr, istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << " "; _err(cerr,++it, args...); } const double pi = 2 * acos(.0); const int inf = 0x3f3f3f3f; const int MOD = 1e9 + 7; template<class T>bool Chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool Chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } template <typename T> istream& operator >> (istream& is, vector<T>& V) { for(auto&& ele : V)is >> ele; return is; } template <typename T> ostream& operator << (ostream& os, const vector<T> V) { os << "["; int cnt = 0; T curr; if(!V.empty()){ for (int i = 0; i < V.size() - 1; ++i) { if(V[i] == curr)cnt ++; else cnt = 0; if(cnt == 4)os << "... "; if(cnt < 4) os << i << ":" << V[i] << " "; curr = V[i]; } os << V.size() - 1 << ":" << V.back(); } os << "]\n"; return os; } template <typename T, typename U> ostream& operator << (ostream& os, const pair<T,U> P) { os << "("; os << P.first << "," << P.second; os << ")"; return os; } template <typename T, typename U> ostream& operator << (ostream& os, const set<T,U> V) { os << "{"; if(!V.empty()){ auto it = V.begin(); for (int i = 0; i < V.size() -1; ++i) { os << *it << " "; it++; } os << *it; } os << "}\n"; return os; } template <typename K, typename H, typename P> ostream& operator << (ostream& os, const unordered_set<K, H, P> V) { os << "{"; if(!V.empty()){ auto it = V.begin(); for (int i = 0; i < V.size() -1; ++i) { os << *it << " "; it++; } os << *it; } os << "}\n"; return os; } template <typename K, typename C> ostream& operator << (ostream& os, const multiset<K, C> V) { os << "{"; if(!V.empty()){ auto it = V.begin(); for (int i = 0; i < V.size() -1; ++i) { os << *it << " "; it++; } os << *it; } os << "}"; return os; } template <typename K, typename T, typename C> ostream& operator << (ostream& os, const map<K,T,C> V) { os << "{"; if(!V.empty()){ auto it = V.begin(); for (int i = 0; i < V.size() -1; ++i) { os << "("; os << it->first << "," << it->second; os << ") "; it++; } os << "("; os << it->first << "," << it->second; os << ")"; } os << "}\n"; return os; } template <typename K, typename T, typename C> ostream& operator << (ostream& os, const unordered_map<K,T,C> V) { os << "{"; if(!V.empty()){ auto it = V.begin(); for (int i = 0; i < V.size() -1; ++i) { os << "("; os << it->first << "," << it->second; os << ") "; it++; } os << "("; os << it->first << "," << it->second; os << ")"; } os << "}\n"; return os; } template <typename T> ostream& operator << (ostream& os, const deque<T> V) { os << "["; if (!V.empty()) { for (int i = 0; i < V.size() - 1; ++i) { os << V[i] << "->"; } if (!V.empty())os << V.back(); } os << "]\n"; return os; }; template <typename T, typename Cont, typename Comp> ostream& operator << (ostream& os, const priority_queue<T, Cont, Comp> V) { priority_queue<T, Cont, Comp> _V = V; os << "["; if(!_V.empty()){ while(_V.size() > 1){ os << _V.top() << "->"; _V.pop(); } os << _V.top(); } os << "]\n"; return os; }; template <class F> struct y_combinator { F f; // the lambda will be stored here // a forwarding operator(): template <class... Args> decltype(auto) operator()(Args&&... args) const { // we pass ourselves to f, then the arguments. // the lambda should take the first argument as `auto&& recurse` or similar. return f(*this, std::forward<Args>(args)...); } }; // helper function that deduces the type of the lambda: template <class F> y_combinator<std::decay_t<F>> recursive(F&& f){ return {std::forward<F>(f)}; } struct hash_pair { template <class T1, class T2> size_t operator()(const pair<T1, T2>& p) const { auto hash1 = hash<T1>{}(p.first); auto hash2 = hash<T2>{}(p.second); return hash1 ^ hash2; } }; template <typename T, typename U> std::vector<T> multi_vector(int n, U v) { return std::vector<T>(n, v); } template <typename U, typename... Args> auto multi_vector(int n, Args... args) { auto val = multi_vector<U>(std::forward<Args>(args)...); return std::vector<decltype(val)>(n, std::move(val)); } //template <signed M, unsigned T> namespace FFT { const int max_base = 18, maxN = 1 << max_base; // N <= 2e5 const double PI = acos(-1); struct num { double x{}, y{}; num() = default; num(double x, double y): x(x), y(y) {} explicit num(double r): x(cos(r)), y(sin(r)) {} }; num operator+(num a, num b) { return {a.x + b.x, a.y + b.y}; } num operator-(num a, num b) { return {a.x - b.x, a.y - b.y}; } num operator*(num a, num b) { return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; } num conj(num a) {return {a.x, -a.y}; } num root[maxN]; int rev[maxN]; bool is_root_prepared = false; void prepare_root(){ if(is_root_prepared) return; is_root_prepared = true; root[1] = num(1, 0); for (int i = 1; i < max_base; ++i) { num x(2*PI / (1LL << (i+1))); for (ll j = (1LL << (i-1)); j < (1LL << (i)); ++j) { root[2*j] = root[j]; root[2*j+1] = root[j]*x; } } } int base, N; int lastN = -1; void prepare_rev(){ if(lastN == N) return; lastN = N; for (int i = 0; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (base - 1)); } void fft(num *a, num *f){ for (int i = 0; i < N; ++i) f[i] = a[rev[i]]; for (int k = 1; k < N; k <<= 1) { for (int i = 0; i < N; i += 2*k) { for (int j = 0; j < k; ++j) { num z = f[i+j+k]* root[j+k]; f[i+j+k] = f[i+j] - z; f[i+j] = f[i+j] + z; } } } } num a[maxN], b[maxN], f[maxN], g[maxN]; ll A[maxN], B[maxN], C[maxN]; void multi_mod(int m){ for (int i = 0; i < N; ++i) { ll x = A[i] % m; a[i] = num(x & ((1LL << 15)-1), x >> 15); } for (int i = 0; i < N; ++i) { ll x = B[i] % m; b[i] = num(x & ((1LL << 15)-1), x >> 15); } fft(a, f); fft(b, g); for (int i = 0; i < N; ++i) { int j = (N-i) &(N-1); num a1 = (f[i] + conj(f[j])) * num(0.5, 0); num a2 = (f[i] - conj(f[j])) * num(0, -0.5); num b1 = (g[i] + conj(g[j])) * num(0.5/N, 0); num b2 = (g[i] - conj(g[j])) * num(0, -0.5/N); a[j] = a1*b1 + a2*b2 * num(0, 1); b[j] = a1*b2 + a2*b1; } fft(a, f); fft(b, g); for (int i = 0; i < N; ++i) { ll aa = f[i].x + 0.5; ll bb = g[i].x + 0.5; ll cc = f[i].y + 0.5; C[i] = (aa + bb % m * (1LL << 15) + cc% m *(1LL << 30)) % m; } } void prepare_AB(int n1, int n2){ base = 1; N = 2; while(N < n1+n2) base++, N <<= 1; for (int i = n1; i < N; ++i) A[i] = 0; for (int i = n2; i < N; ++i) B[i] = 0; prepare_root(); prepare_rev(); } void multi_mod(int n1, int n2, int m){ prepare_AB(n1, n2); multi_mod(m); } } struct poly { vector<int> v; poly() = default; explicit poly(vector<int> vv) : v(std::move(vv)) {}; int size() {return (int)v.size(); } poly cut(int len){ if(len < v.size()) v.resize(static_cast<unsigned long>(len)); return *this; } inline int& operator[] (int i) {return v[i]; } }; poly operator+(poly &A, poly &B){ poly C; C.v = vector<int>(max(A.size(), B.size())); for (int i = 0; i < A.size(); ++i) C[i] = A[i]; for (int i = 0; i < B.size(); ++i) (C[i] += B[i]) %= MOD; return C; } poly operator-(poly &A, poly &B){ poly C; C.v = vector<int>(max(A.size(), B.size())); for (int i = 0; i < A.size(); ++i) C[i] = A[i]; for (int i = 0; i < B.size(); ++i) (C[i] += MOD-B[i]) %= MOD; return C; } poly operator* (poly &A, poly &B){ poly C; C.v = vector<int>(A.size() + B.size()-1); for (int i = 0; i < A.size(); ++i) FFT::A[i] = A[i]; for (int i = 0; i < B.size(); ++i) FFT::B[i] = B[i]; FFT::multi_mod(A.size(), B.size(), MOD); for (int i = 0; i < C.size(); ++i) C[i] = FFT::C[i]; return C; } template<typename T> T extgcd(T a, T b, T &x ,T &y){ for (T u = y = 1, v = x = 0; a; ) { ll q = b/a; swap(x -= q*u, u); swap(y -= q*v, v); swap(b -= q*a, a); } return b; } template<typename T> T mod_inv(T x, T m){ T s, t; extgcd(x, m, s, t); return (m+s)% m; } poly inv (poly f){ int n = f.size(); vector<int> rr(1, mod_inv(f[0], MOD)); poly r(rr); for (int k = 2; k <= n; k <<= 1) { vector<int> v(k); for (int i = 0; i < k; ++i) { v[i] = f[i]; } poly ff(v); poly nr = (r*r); nr = nr*ff; nr.cut(k); for (int i = 0; i < k/2; ++i) { nr[i] = (2*r[i]-nr[i]+MOD)%MOD; nr[i+k/2] = (MOD-nr[i+k/2])%MOD; } r = nr; } return r; } class No3046Yukicoder { public: void solve(std::istream& cin, std::ostream& cout, std::ostream& cerr) { int k, n; cin >> k >> n; vector<int> v(n); for (auto &&i : v) { cin >> i; } vector<int> p(2e5+5, 0); for (int i = 0; i < n; ++i) { p[v[i]] = MOD-1; } p[0] = 1; poly pp(p); poly ppinv = inv(pp); cout << ppinv[k] << "\n"; } }; #undef int int main() { No3046Yukicoder solver; std::istream& in(std::cin); std::ostream& out(std::cout); std::ostringstream err; in.tie(0); ios::sync_with_stdio(0); solver.solve(in, out,err); return 0; }