結果

問題 No.3046 yukicoderの過去問
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2020-08-28 17:13:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 371 ms / 2,000 ms
コード長 8,448 bytes
コンパイル時間 4,185 ms
コンパイル使用メモリ 178,144 KB
実行使用メモリ 23,072 KB
最終ジャッジ日時 2024-11-13 23:28:22
合計ジャッジ時間 5,152 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,824 KB
testcase_03 AC 360 ms
22,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 360 ms
22,940 KB
testcase_06 AC 371 ms
23,072 KB
testcase_07 AC 365 ms
23,072 KB
testcase_08 AC 367 ms
23,072 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:238:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  238 |         int p;scanf("%d",&p);
      |               ~~~~~^~~~~~~~~

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.28 17:13:15
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;




template < const int MOD , const int root = 3 , bool any = false>
struct FormalPowerSeries {
private:
    using P = FormalPowerSeries< MOD, root, any >;
    vector< long long > v;
    
    
    long long powMod(long long k, long long n, long long mod) const {
        ll x = 1;
        while (n > 0) {
            if (n & 1) {
                x = x * k % mod;
            }
            k = k * k % mod;
            n >>= 1;
        }
        return x;
    }
    void ntt(const bool rev = false) {
        unsigned int i, j, k, l, p, q, r, s;
        const unsigned int sz = this->v.size();
        if(sz == 1) return;
        vector<long long> a(sz);
        r = rev ? (MOD - 1 - (MOD - 1) / sz) : (MOD - 1) / sz;
        s = powMod(root, r, MOD);
        vector<unsigned int> kp(sz / 2 + 1, 1);
        for(i = 0; i < sz / 2; ++i) kp[i + 1] = (unsigned long long)kp[i] * s % MOD;
        for(i = 1, l = sz / 2; i < sz; i <<= 1, l >>= 1){
            for(j = 0, r = 0; j < l; ++j, r += i){
                for(k = 0, s = kp[i * j]; k < i; ++k){
                    p = this->v[k + r], q = this->v[k + r + sz / 2];
                    a[k + 2 * r] = (p + q) % MOD;
                    a[k + 2 * r + i] = (unsigned long long)((p - q + MOD) % MOD) * s % MOD;
                }
            }
            swap(this->v, a);
        }
        if(rev){
            s = powMod(sz,MOD-2,MOD);
            for(i = 0; i < sz; i++){ this->v[i] = (unsigned long long)this->v[i] * s % MOD; }
        }
    }
    inline P pre(int sz) const {
        return P(vector<long long>(this->v.begin(), this->v.begin() + min((int) this->v.size(), sz)));
    }
public:
    FormalPowerSeries(int sz = 0) {
        this->v.resize(sz, 0);
    }
    FormalPowerSeries(const vector<long long> &v) {
        this->v.resize(v.size());
        for (int i = 0; i < v.size(); i++) {
            this->v[i] = v[i];
        }
    }
    
    inline size_t size() const { return this->v.size(); }
    inline void resize(int x, long long val = 0) {
        assert(x >= 0);
        this->v.resize(x,val);
    }
    inline void set(int x, long long val) {
        assert(0 <= x && x < (int)v.size());
        this->v[x] = (val % MOD + MOD) % MOD;
    }
    P operator+(const P &a) const { return P(*this) += a; }
    P operator+(const long long a) const { return P(*this) += a; }
    P operator-(const P &a) const { return P(*this) -= a; }
    P operator*(const P &a) const { return P(*this) *= a; }
    P operator*(const long long a) const { return P(*this) *= a; }
    P operator/(const P &a) const { return P(*this) /= a; }
    P &operator+=(const P &a) {
        if (a.size() > this->v.size()) this->v.resize(a.size(), 0);
        for (int i = 0; i < a.size(); i++) this->v[i] += a[i], this->v[i] %= MOD;
        return *this;
    }
    P &operator+=(const long long a) {
        if (this->v.size() == 0) this->v.resize(1,(a % MOD + MOD) % MOD);
        else this->v[0] += a, this->v[0] %= MOD;
        return *this;
    }
    P &operator-=(const P &a) {
        if (a.size() > this->v.size()) this->v.resize(a.size(), 0);
        for (int i = 0; i < a.size(); i++) this->v[i] = this->v[i] - a[i] + MOD, this->v[i] %= MOD;
        while (this->size() && this->v.back() == 0) this->v.pop_back();
        return *this;
    }
    P &operator*=(const long long a) {
        for (int i = 0; i < this->v.size(); i++) this->v[i] *= a, this->v[i] %= MOD;
        return *this;
    }
    P &operator*=(const P &a) {
        if (this->v.empty() || (int)a.size() == 0) {
            this->v.clear();
            return *this;
        }
        if (any) {
            int n = this->v.size(), m = a.size();
            static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;
            using T0 = FormalPowerSeries<mod0,3>;
            using T1 = FormalPowerSeries<mod1,3>;
            using T2 = FormalPowerSeries<mod2,5>;
            T0 l0(n), r0(m);
            T1 l1(n), r1(m);
            T2 l2(n), r2(m);
            for (int i = 0; i < n; ++i) l0.set(i,this->v[i]), l1.set(i,this->v[i]), l2.set(i,this->v[i]);
            for (int j = 0; j < m; ++j) r0.set(j,a[j]), r1.set(j,a[j]), r2.set(j,a[j]);
            l0 = l0 * r0, l1 = l1 * r1, l2 = l2 * r2;
            this->v.resize(n + m - 1);
            static const long long im0 = powMod(mod0, mod1-2, mod1);
            static const long long im1 = powMod(mod1, mod2-2, mod2), im0m1 = im1 * powMod(mod0, mod2-2, mod2) % mod2;
            static const long long m0 = mod0 % MOD, m0m1 = m0 * mod1 % MOD;
            for (int i = 0; i < n + m - 1; ++i) {
                int y0 = l0[i];
                int y1 = (im0 * (l1[i] - y0 + mod1)) % mod1;
                int y2 = (im0m1 * (l2[i] - y0 + mod2) % mod2 - im1 * y1 % mod2 + mod2) % mod2;
                this->v[i] = (y0 + m0 * y1 % MOD + m0m1 * y2 % MOD) % MOD;
            }
            return *this;
        }
        else {
            const int sz = (int)this->v.size() + (int)a.size() - 1;
            int t = 1;
            while(t < sz){ t <<= 1; }
            P A(t); this->v.resize(t,0);
            for(int i = 0; i < (int)a.size(); i++){ A.set(i,a[i]); }
            this->ntt(), A.ntt();
            for (int i = 0; i < t; i++){ this->v[i] = (unsigned long long)this->v[i] * A[i] % MOD; }
            this->ntt(true);
            this->v.resize(sz);
            
            return *this;
        }
    }
    
    P &operator/=(const P &a) {
        *this *= a.inverse();
        return *this;
    }
    
    P inverse(int deg = -1) const {
        assert(this->v.size() != 0 && this->v[0] != 0);
        const int n = (int)this->v.size();
        if(deg == -1) deg = n;
        P ret(1);
        ret.set(0,powMod(this->v[0],MOD-2,MOD)); 
        for(int i = 1; i < deg; i <<= 1) {
            ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
        }
        return ret.pre(deg);
    }
    
    P differential() const {
        const int n = (int) this->v.size();
        P ret(max(0, n - 1));
        for(int i = 1; i < n; i++) ret.set(i-1,this->v[i] * i);
        return ret;
    }
    
    P integral() const {
        const int n = (int) this->v.size();
        P ret(n + 1);
        for(int i = 0; i < n; i++) ret.set(i + 1,this->v[i] * powMod(i + 1,MOD-2,MOD));
        return ret;
    }
    
    
    P log(int deg = -1) const {
        assert(this->v.size() != 0 && this->v[0] == 1);
        const int n = (int)this->v.size();
        if(deg == -1) deg = n;
        return (this->differential() * this->inverse(deg)).pre(deg - 1).integral();
    }
    
    P exp(int deg = -1) const {
        if (this->v.size() == 0) return P(0);
        assert(this->v[0] == 0);
        const int n = (int) this->v.size();
        if(deg == -1) deg = n;
        P ret(1);
        ret.set(0,1);
        for(int i = 1; i < deg; i <<= 1) {
            ret = (ret * (pre(i << 1) + 1 - ret.log(i << 1))).pre(i << 1);
        }
        return ret.pre(deg);
    }
    
    P pow(long long k, int deg = -1) const {
        const int n = (int) this->v.size();
        if(deg == -1) deg = n;
        for(int i = 0; i < n; i++) {
            if(this->v[i] != 0) {
                long long rev = powMod(this->v[i],MOD-2,MOD);
                P C = *this * rev;
                P D(n - i);
                for(int j = i; j < n; j++) D.set(j - i,C[j]);
                D = (D.log() * k).exp() * powMod(this->v[i],k,MOD);
                P E(deg);
                if(i * k > deg) return E;
                auto S = i * k;
                for(int j = 0; j + S < deg && j < D.size(); j++) E.set(j + S,D[j]);
                return E;
            }
        }
        return *this;
    }
    inline long long operator[](int x) const {
        assert(0 <= x && x < (int)this->v.size());
        return v[x];
    }
    friend std::ostream &operator<<(std::ostream &os, const P &p) {
        os << "[ ";
        for (int i = 0; i < (int)p.size(); i++) {
            os << p[i] << " ";
        }
        os << "]";
        return os;
    }
};
int main() {
    int k,n;cin >> k >> n;
    FormalPowerSeries<1000000007,3,true> a(k+1);
    a.set(0,1);
    for (int i = 0; i < n; i++) {
        int p;scanf("%d",&p);
        if (p <= k) a.set(p,-1);
    }
    a = a.inverse();
    cout << a[k] << endl;
    return 0;
}
0