結果
問題 | No.3046 yukicoderの過去問 |
ユーザー | potetisensei |
提出日時 | 2019-12-10 18:15:53 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 393 ms / 2,000 ms |
コード長 | 7,431 bytes |
コンパイル時間 | 2,263 ms |
コンパイル使用メモリ | 187,976 KB |
実行使用メモリ | 78,620 KB |
最終ジャッジ日時 | 2024-06-24 02:04:39 |
合計ジャッジ時間 | 5,433 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 116 ms
45,312 KB |
testcase_01 | AC | 123 ms
45,300 KB |
testcase_02 | AC | 123 ms
45,304 KB |
testcase_03 | AC | 345 ms
75,012 KB |
testcase_04 | AC | 123 ms
45,312 KB |
testcase_05 | AC | 382 ms
78,620 KB |
testcase_06 | AC | 393 ms
78,620 KB |
testcase_07 | AC | 390 ms
78,588 KB |
testcase_08 | AC | 390 ms
78,620 KB |
ソースコード
#include<bits/stdc++.h> #define XX first #define YY second #define pb emplace_back #define FOR(i,a,b) for(int (i)=(a);i<(b);++(i)) #define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i)) #define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X)) #define REP rep #define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X)) #define all(X) (X).begin(),(X).end() #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef ll LL; typedef pii PII; typedef pll PLL; const ll MOD=1e9+7; #define rall(X) (X).rbegin(),(X).rend() #define UNIQUE(X) (X).erase(unique(all(X)),(X).end()) #define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X)) #define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X)) template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;} template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;} template<ll mod> struct ModInt{ using M=ModInt; ll a; M& put(ll v){ a=(v<mod)?v:v-mod; return *this; } ModInt(ll v=0){put(v%mod+mod);} inline M operator+(const M &x){return M().put(a+x.a);} inline M operator-(const M &x){return M().put(a+mod-x.a);} inline M operator*(const M &x){return M().put(a*x.a%mod);} inline M operator/(M x){return x.inv()*a;} inline M& operator+=(const M &x){return *this=*this+x;}; inline M& operator-=(const M &x){return *this=*this-x;}; inline M& operator*=(const M &x){return *this=*this*x;}; inline M& operator/=(const M &x){return *this=*this/x;}; inline bool operator==(const M &x){return a==x.a;} inline M pow(ll m){ M x=*this,res=1; while(m){ if(m&1)res*=x; x*=x; m>>=1; } return res; } inline M inv(){return pow(mod-2);} }; using mint = ModInt<MOD>; using C = complex<double>; namespace std { template<> C& C::operator*=(const C& y) { double a = this->real(); double b = this->imag(); double c = y.real(); double d = y.imag(); return *this=C(a*c-b*d, a*d+b*c); } } template<int B> // n <= 1<<B struct FFT{ vector<int> m2[B+1]; vector<C> power[B+1]; FFT(){ rep(e, B+1){ int lim = 1 << e; m2[e].resize(lim); power[e].resize(lim); rep(st, lim) power[e][st] = polar(1.0, M_PI*st/lim); rep(i, e) rep(st, lim) if(st >> i & 1) m2[e][st] |= 1 << e-1-i; } } void Dft(C *f, int lim) { int e = 31 - __builtin_clz(lim); assert(e <= B); assert(1 << e == lim); rep(st, lim) if(st < m2[e][st]) swap(f[st], f[m2[e][st]]); rep(k, e) { int t = 1 << k; int w = 1 << k+1; C *po = power[k].data(); for (int i=0; i<lim; i+=w) { rep(j, t) { C x = f[i+j]; C y = f[i+j+t] * po[j]; f[i+j] = x + y; f[i+j+t] = x - y; } } } } template <class T> vector<C> Conv(vector<T> &f, vector<T> &g) { int n = f.size() + g.size() - 1; int lim = 2; while (lim < n) lim <<= 1; vector<C> cf(all(f)); vector<C> cg(all(g)); cf.resize(lim); cg.resize(lim); Dft(cf.data(), lim); Dft(cg.data(), lim); rep(i, lim) cf[i] = conj(cf[i] * cg[i])/double(lim); Dft(cf.data(), lim); assert(0); // DO conj one more if using complex numbers !!! cf.resize(n); return cf; } vector<LL> Conv2(vector<LL> &f, vector<LL> &g, LL mod) { int n = f.size(); int m = g.size(); int lim = 2; while (lim < n+m) lim <<= 1; const int D = 2; const int L = 15; const int M = (1 << L) - 1; vector<C> cs[D]; vector<C> ds[D]; vector<C> es[D]; rep(i, D) { cs[i].resize(lim+10); ds[i].resize(lim+10); es[i].resize(lim+10); rep(j, n) es[i][j].real(f[j] >> (i*L) & M); rep(j, m) es[i][j].imag(g[j] >> (i*L) & M); Dft(es[i].data(), lim); rep(j, lim) { int nj = (lim-j) & (lim-1); cs[i][j] = es[i][j] + conj(es[i][nj]); ds[i][j] = es[i][j] - conj(es[i][nj]); } es[i].assign(lim, C()); } rep(i, D) { rep(j, D) { rep(k, lim) { int r = (i+j) >> 1; int m = (i+j) % 2; es[r][k] += cs[i][k] * ds[j][k] * polar(0.25, (m-1) * M_PI/2); } } } rep(i, D) { rep(j, lim) es[i][j] = conj(es[i][j])/double(lim); Dft(es[i].data(), lim); } vector<LL> ret(n+m-1); rep(j, ret.size()) { LL mul = 1; rep(i, D*2-1) { LL v; if (i%2) { v = llround(-es[i/2][j].imag()) % mod; } else { v = llround(es[i/2][j].real()) % mod; } ret[j] += v * mul; ret[j] %= mod; mul <<= L; mul %= mod; } } return ret; } }; FFT<20> fft; struct Poly : public vector<mint> { using vector<mint>::vector; template<class... A> Poly(A... a) : vector<mint>(a...) {} inline void normalize() { while (size() && back() == 0) pop_back(); } inline mint coef(int i) const {return i < size() ? (*this)[i] : mint(0);} Poly operator+(const Poly &x) { auto res = *this; res.resize(max(size(), x.size())); rep(i, x.size()) res[i] += x[i]; return res; } Poly operator-(const Poly &x){ auto res = *this; res.resize(max(size(), x.size())); rep(i, x.size()) res[i] -= x[i]; return res; } Poly operator*(const Poly& x) { vector<LL> f, g; // MOD=1e9+7の時 for (auto v : x) f.eb(v.a); for (auto v : *this) g.eb(v.a); auto res = fft.Conv2(f, g, MOD); return Poly(all(res)); } Poly operator*(mint x) { auto res = *this; rep(i, size()) res[i] *= x; return res; } Poly operator/(mint x){ auto res = *this; rep(i, size()) res[i] /= x; return res; } Poly& operator+=(const Poly& x){return *this=(*this)+x;} Poly& operator-=(const Poly& x){return *this=(*this)-x;} Poly& operator*=(const Poly& x){return *this=(*this)*x;} Poly& operator*=(mint x){return *this=(*this)*x;} Poly& operator/=(mint x){return *this=(*this)/x;} Poly pre(int n) { return Poly(begin(), begin()+min(n,(int)size())); } Poly rev() { auto res=*this; reverse(all(res)); return res; } Poly diff(int n){ MN(n, (int)size()); Poly res(n); reps(i, 1, n+1) res[i-1] = coef(i)*i; return res; } Poly inte(int n){ MN(n, (int)size()+1); Poly res(n); reps(i, 1, n) res[i] = coef(i-1)/i; return res; } Poly inv(int m) { // a_0 != 0 Poly res(1, mint(1)/coef(0)); for (int i=1; i<m; i*=2) { res = (res+res-res*res*pre(2*i)).pre(2*i); } return res.pre(m); } Poly log(int n) { // a_0 = 1 return (diff(n-1)*inv(n-1)).inte(n); } Poly exp(int n) { // a_0 = 0 Poly f{1}; for (int i=1; i<n; i*=2) { f = (f*(pre(2*i)-f.log(2*i))+f).pre(2*i); } return f.pre(n); } Poly div(Poly g) { auto f = *this; f.normalize(); g.normalize(); if (f.size() < g.size()) return Poly(); reverse(all(f)); reverse(all(g)); int d = f.size() - g.size() + 1; Poly ret = (f * g.inv(d)).pre(d); reverse(all(ret)); return ret; } }; ostream& operator<<(ostream& ost,Poly a) { rep(i, a.size()) { if (i) cout<<" "; cout<<a[i].a; } return ost; } int K, N; signed main(){ ios_base::sync_with_stdio(false); cout<<fixed<<setprecision(0); cin >> K >> N; Poly e{1}; Poly f(114514); rep(i, N) { int x; cin >> x; f[x] += 1; } f.normalize(); cout << (e-f).inv(K+1)[K].a << endl; }