#508004 (C++17) No.8046 yukicoderの過去問

• 問題: No.8046 yukicoderの過去問
• ユーザー: potetisensei
• 提出日時: 2020-07-08 00:45:03
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 783 ms / 2,000 ms
• コード長: 7,478 bytes
• コンパイル時間: 2,667 ms
• コンパイル使用メモリ: 214,424 KB
• 最終ジャッジ日時: 2025-01-11 16:45:23
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
other	AC * 9

ソースコード

#include<bits/stdc++.h>
using LD = long double;
#define double LD
#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.25l, (m-1) * LD(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;
}