結果
問題 | No.8046 yukicoderの過去問 |
ユーザー | Taiki0715 |
提出日時 | 2023-11-20 17:12:48 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,203 ms / 2,000 ms |
コード長 | 4,107 bytes |
コンパイル時間 | 6,114 ms |
コンパイル使用メモリ | 186,068 KB |
実行使用メモリ | 10,740 KB |
最終ジャッジ日時 | 2024-09-26 06:40:05 |
合計ジャッジ時間 | 10,485 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1,146 ms
10,736 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1,146 ms
10,736 KB |
testcase_06 | AC | 1,179 ms
10,740 KB |
testcase_07 | AC | 1,182 ms
10,740 KB |
testcase_08 | AC | 1,203 ms
10,740 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast<void>(0) #define debugg(...) static_cast<void>(0) template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;} #endif using ll=long long; using ull=unsigned long long; using P=pair<ll,ll>; template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>; template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);} template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;} template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;} template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;} template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;} template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} template<typename T,size_t n,size_t id=0> auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL clock_t start=clock(); #endif int testcase=1; //cin>>testcase; for(int i=0;i<testcase;i++){ SOLVE(); } #ifdef LOCAL cerr<<"time:"; cerr<<(clock()-start)/1000; cerr<<"ms\n"; #endif } int garner(vector<pair<int,int>>r,int mod){ r.emplace_back(0,mod); vector<ll>a(r.size(),1),b(r.size(),0); rep(i,r.size()-1){ ll v=(r[i].first-b[i])*inv_mod(a[i],r[i].second)%r[i].second; if(v<0)v+=r[i].second; reps(j,i+1,r.size()){ b[j]+=a[j]*v; b[j]%=r[j].second; a[j]*=r[i].second; a[j]%=r[j].second; } } return b[r.size()-1]; } template<typename T> vector<T>anymod_convolution(const vector<T>&a,const vector<T>&b){ if(a.empty()||b.empty())return vector<T>{}; if(min(a.size(),b.size())<60){ vector<T>ret(a.size()+b.size()-1,0); rep(i,a.size())rep(j,b.size())ret[i+j]+=a[i]*b[j]; return ret; } using mint1=static_modint<167772161>; using mint2=static_modint<469762049>; using mint3=static_modint<1224736769>; vector<mint1>a1(a.size()),b1(b.size()); vector<mint2>a2(a.size()),b2(b.size()); vector<mint3>a3(a.size()),b3(b.size()); rep(i,a.size()){ a1[i]=a[i].val(); a2[i]=a[i].val(); a3[i]=a[i].val(); } rep(i,b.size()){ b1[i]=b[i].val(); b2[i]=b[i].val(); b3[i]=b[i].val(); } a1=convolution(a1,b1),a2=convolution(a2,b2),a3=convolution(a3,b3); vector<T>ret(a.size()+b.size()-1); rep(i,ret.size()){ vector<pair<int,int>>r(3); r[0].first=a1[i].val(),r[0].second=mint1::mod(); r[1].first=a2[i].val(),r[1].second=mint2::mod(); r[2].first=a3[i].val(),r[2].second=mint3::mod(); ret[i]=garner(r,T::mod()); } return ret; } using mint=modint1000000007; void SOLVE(){ int k,n; cin>>k>>n; vector<mint>coef(k+1,0); rep(i,n){ int x; cin>>x; if(x<=k)coef[x]=1; } vector<mint>dp(k+1,0); dp[0]=1; auto solve=[&](auto self,int l,int r){ if(l+1==r)return; int mid=(l+r)/2; self(self,l,mid); vector<mint>f{dp.begin()+l,dp.begin()+mid}; vector<mint>g{coef.begin(),coef.begin()+r-l}; vector<mint>c=anymod_convolution(f,g); rep(i,c.size())if(mid<=l+i&&l+i<r)dp[i+l]+=c[i]; self(self,mid,r); }; solve(solve,0,k+1); cout<<dp[k].val()<<endl; }