結果

問題 No.8046 yukicoderの過去問
ユーザー hashiryohashiryo
提出日時 2019-07-09 11:53:24
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 514 ms / 2,000 ms
コード長 5,095 bytes
コンパイル時間 2,217 ms
コンパイル使用メモリ 184,440 KB
実行使用メモリ 23,748 KB
最終ジャッジ日時 2024-10-11 22:23:48
合計ジャッジ時間 7,822 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 505 ms
23,512 KB
testcase_01 AC 501 ms
23,632 KB
testcase_02 AC 506 ms
23,748 KB
testcase_03 AC 502 ms
23,508 KB
testcase_04 AC 504 ms
23,504 KB
testcase_05 AC 505 ms
23,624 KB
testcase_06 AC 510 ms
23,636 KB
testcase_07 AC 514 ms
23,532 KB
testcase_08 AC 513 ms
23,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/2;
const ll MOD = 1e9+7;

inline ll add(ll a, ll b, ll M) { // a + b (mod M)
    return (a += b) >= M ? a - M : a;
}
inline ll sub(ll a, ll b, ll M) { // a - b (mod M)
    return (a -= b) < 0 ? a + M : a;
}
inline ll mul(ll a, ll b, ll M) { // a * b (mod M)
    ll r = a*b - (ll)((long double)(a)*b/M+.5)*M;
    return r < 0 ? r + M: r;
}
inline ll div(ll a, ll b, ll M) { // solve b x == a (mod M)
    ll u = 1, x = 0, s = b, t = M;
    while (s) { // extgcd for b x + M s = t
        ll q = t / s;
        swap(x -= u * q, u);
        swap(t -= s * q, s);
    }
    if (a % t) return -1; // infeasible
    return mul(x < 0 ? x + M : x, a / t, M); // b (xa/t) == a (mod M)
}
inline ll pow(ll a, ll b, ll M) {
    ll x = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1) x = (a * x) % M;
        a = (a * a) % M;
    }
    return x;
}

// p(x) = p[0] + p[1] x + ... + p[n-1] x^n-1
// assertion: p.back() != 0
typedef vector<ll> poly;
ostream& operator<<(ostream &os, const poly &p) {
    bool head = true;
    for (size_t i = 0; i < p.size(); ++i) {
        if (p[i] == 0) continue;
        if (!head) os << " + ";
        os << p[i];
        head = false;
        if (i >= 1) os << " x";
        if (i >= 2) os << "^" << i;
    }
    return os;
}
inline poly add(poly p, const poly &q, ll M) {
    if (p.size() < q.size()) p.resize(q.size());
    for (size_t i = 0; i < q.size(); ++i)
        p[i] = add(p[i], q[i], M);
    while (!p.empty() && !p.back()) p.pop_back();
    return p;
}
inline poly sub(poly p, const poly &q, ll M) {
    if (p.size() < q.size()) p.resize(q.size());
    for (size_t i = 0; i < q.size(); ++i)
        p[i] = sub(p[i], q[i], M);
    while (!p.empty() && !p.back()) p.pop_back();
    return p;
}



// FFT-based multiplication: this works correctly for M in [int]
// assume: size of a/b is power of two, mod is predetermined
template <int mod, int sign>
inline void fmt(vector<ll>& x) {
    const int n = x.size();
    int h = pow(3, (mod-1)/n, mod);
    if (sign < 0) h = div(1, h, mod);
    for (int i = 0, j = 1; j < n-1; ++j) {
        for (int k = n >> 1; k > (i ^= k); k >>= 1);
        if (j < i) swap(x[i], x[j]);
    }
    for (int m = 1; m < n; m *= 2) {
        ll w = 1, wk = pow(h, n / (2*m), mod);
        for (int i = 0; i < m; ++i) {
            for (int s = i; s < n; s += 2*m) {
                ll u = x[s], d = x[s + m] * w % mod;
                if ((x[s] = u + d) >= mod) x[s] -= mod;
                if ((x[s + m] = u - d) < 0) x[s + m] += mod;
            }
            w = w * wk % mod;
        }
    }
    if (sign < 0) {
        ll inv = div(1, n, mod);
        for (auto &a: x)
            a = a * inv % mod;
    }
}
// assume: size of a/b is power of two, mod is predetermined
template <int mod>
inline vector<ll> conv(vector<ll> a, vector<ll> b){
    fmt<mod,+1>(a); fmt<mod,+1>(b);
    for (size_t i = 0; i < a.size(); ++i)
        a[i] = a[i] * b[i] % mod;
    fmt<mod,-1>(a);
    return a;
}
// general convolution where mod < 2^31.
inline vector<ll> conv(vector<ll> a, vector<ll> b, ll mod){
    int n = a.size() + b.size() - 1;
    for (int k: {1,2,4,8,16}) n |= (n >> k);
    ++n;
    a.resize(n); b.resize(n);
    const int A = 167772161, B = 469762049, C = 1224736769, D = (ll)(A) * B % mod;
    vector<ll> x = conv<A>(a,b), y = conv<B>(a,b), z = conv<C>(a,b);
    for (size_t i = 0; i < x.size(); ++i) {
        ll X = (y[i] - x[i]) * 104391568;
        if ((X %= B) < 0) X += B;
        ll Y = (z[i] - (x[i] + A * X) % C) * 721017874;
        if ((Y %= C) < 0) Y += C;
        x[i] += A * X + D * Y;
        if ((x[i] %= mod) < 0) x[i] += mod;
    }
    x.resize(n);
    return x;
}
inline poly mul(poly p, poly q, ll M) {
    poly pq = conv(p, q, M);
    pq.resize(p.size() + q.size() - 1);
    while (!pq.empty() && !pq.back()) pq.pop_back();
    return pq;
}


poly inv(poly f,ll M){
    size_t n=f.size();
    poly t = {div(1, f[0], M)};
    if (t[0] < 0) return { {}, {} }; // infeasible
    poly ff(1,f[0]);
    for (size_t k = 2; k <= n; k <<= 1) {
        for(size_t i=k/2;i<k;i++)ff.push_back(f[i]);
        poly s = mul(mul(t, t, M), ff, M);
        s.resize(k);
        for (size_t i = 0; i < k/2; ++i){
            s[i] = sub(2*t[i], s[i], M);
            s[i+k/2] = sub(0, s[i+k/2], M);
        }
        t=s;
    }
    return t;
}
#include <ctime>
double tick() {
  static clock_t oldtick;
  clock_t newtick = clock();
  double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
  oldtick = newtick;
  return diff;
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //tick();
  ll K;cin>>K;
  ll N;cin>>N;
  poly f(1<<17,0);
  for(ll i=0;i<N;i++){
    ll x;cin>>x;
    f[x]=MOD-1;
  }
  f[0]=1;
  auto g=inv(f,MOD);
  cout<<g[K]<<endl;
  //cerr<<tick()<<endl;
  return 0;
}
0