結果

問題 No.3046 yukicoderの過去問
ユーザー chocoruskchocorusk
提出日時 2019-04-05 13:26:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 379 ms / 2,000 ms
コード長 3,802 bytes
コンパイル時間 1,186 ms
コンパイル使用メモリ 112,036 KB
実行使用メモリ 43,852 KB
最終ジャッジ日時 2024-06-11 07:37:57
合計ジャッジ時間 3,587 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
8,960 KB
testcase_01 AC 11 ms
8,960 KB
testcase_02 AC 11 ms
8,960 KB
testcase_03 AC 345 ms
43,720 KB
testcase_04 AC 11 ms
9,088 KB
testcase_05 AC 347 ms
43,724 KB
testcase_06 AC 368 ms
43,852 KB
testcase_07 AC 355 ms
43,724 KB
testcase_08 AC 379 ms
43,852 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
//#define double long double
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const int MOD=1e9+7;
typedef complex<double> Cd;
const double PI=acos(-1.0);
vector<Cd> tmp;
size_t sz;
vector<Cd> rots;
const int N=1<<18;
void init(){
    rots.resize(N+1);
    for(int j=0; j<=N; j++){
        rots[j].real(cos(2*PI*j/N));
        rots[j].imag(sin(2*PI*j/N));
    }
}
vector<Cd> fft(vector<Cd> a, bool inv=false){
    size_t mask=sz-1;
    size_t p=0;
    for(size_t i=sz>>1; i>0; i>>=1){
        auto& cur=((p&1) ? tmp : a);
        auto& nex=((p&1) ? a : tmp);
        //Cd e=polar((double)1.0, 2*PI*i*(inv ? -1.0 : 1.0)/sz);
        Cd w;
        size_t d=i*(N/sz), t=(inv ? N : 0);
        for(size_t j=0; j<sz; j+=i){
            w=rots[t];
            for(size_t k=0; k<i; k++){
                nex[j+k]=cur[((j<<1)&mask)+k]+w*cur[(((j<<1)+i)&mask)+k];
            }
            if(inv) t-=d;
            else t+=d;
            //w*=e;
        }
        p++;
    }
    if(p&1) swap(a, tmp);
    if(inv) for(size_t i=0; i<sz; i++) a[i]/=sz;
    return a;
}
/*vector<int> convolution(vector<int> a, vector<int> b){
    size_t m=a.size()+b.size()-1;
    sz=1;
    while(sz<m) sz<<=1;
    tmp.resize(sz);
    vector<Cd> A(sz), B(sz);
    for(size_t i=0; i<a.size(); i++) A[i].real(a[i]);
    for(size_t i=0; i<b.size(); i++) A[i].imag(b[i]);
    A=fft(A);
    for(size_t i=0; i<sz; i++){
        Cd x=(A[i]+conj(A[(sz-i)%sz]))*Cd(0.5, 0);
        Cd y=(A[i]-conj(A[(sz-i)%sz]))*Cd(0, -0.5);
        B[i]=x*y;
    }
    B=fft(B, true);
    vector<int> ans(m);
    for(size_t i=0; i<m; i++) ans[i]=round(B[i].real());
    return ans;
}*/
vector<ll> convolution(vector<ll> a, vector<ll> b){
    size_t m=a.size()+b.size()-1;
    sz=1;
    while(sz<m) sz<<=1;
    tmp.resize(sz);
    ll mask=(1<<15)-1;
    vector<Cd> A(sz), B(sz), C(sz), D(sz);
    for(size_t i=0; i<a.size(); i++) A[i]=Cd(a[i]&mask, a[i]>>15);
    for(size_t i=0; i<b.size(); i++) B[i]=Cd(b[i]&mask, b[i]>>15);
    A=fft(A); B=fft(B);
    for(size_t i=0; i<sz; i++){
        size_t j=(sz-i)%sz;
        Cd AL=(A[i]+conj(A[j]))*Cd(0.5, 0);
        Cd AH=(A[i]-conj(A[j]))*Cd(0, -0.5);
        Cd BL=(B[i]+conj(B[j]))*Cd(0.5, 0);
        Cd BH=(B[i]-conj(B[j]))*Cd(0, -0.5);
        C[i]=AL*BL+AH*BL*Cd(0, 1.0);
        D[i]=AL*BH+AH*BH*Cd(0, 1.0);
    }
    C=fft(C, true);
    D=fft(D, true);
    vector<ll> ans(sz);
    for(size_t i=0; i<sz; i++){
        ll x=(ll)round(C[i].real())%MOD;
        ll y=((ll)round(C[i].imag())+(ll)round(D[i].real()))%MOD;
        ll z=(ll)round(D[i].imag())%MOD;
        ans[i]=(x+(y<<15)+(z<<30))%MOD;
        ans[i]=(ans[i]+MOD)%MOD;
    }
    return ans;
}

ll solve(vector<ll> p, int k){
    vector<ll> p0; p0.push_back(p[0]);
    vector<ll> ret(1, 1);
    int i=0;
    while((1<<i)<=k){
        for(int j=(1<<i); j<min(100001, 1<<(i+1)); j++){
            p0.push_back(p[j]);
        }
        i++;
        vector<ll> p1=convolution(ret, p0);
        p1.resize(1<<i);
        for(int j=0; j<p1.size(); j++){
            if(j==0) p1[0]=(2-p1[0]+MOD)%MOD;
            else p1[j]=(MOD-p1[j])%MOD;
        }
        ret=convolution(ret, p1);
        ret.resize(1<<i);
    }
    return ret[k];
}

int main()
{
    int k, n; cin>>k>>n;
    vector<ll> p(100001, 0);
    p[0]=1;
    for(int i=0; i<n; i++){
        int x; cin>>x;
        p[x]=MOD-1;
    }
    init();
    cout<<solve(p, k)<<endl;
    return 0;
}
0