This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://yukicoder.me/problems/2017" #include "../template.hpp" #include "../type/modint.hpp" #include "../Math/Precalc.hpp" #include "../Math/FormalPowerSeriesNaive.hpp" using mint=ModInt<1000000007>; Precalc<mint> F(500000); using FPS=FormalPowerSeriesNaive<mint>; signed main(){ int n,k;cin>>n>>k; rep(i,n){int a;cin>>a;} FPS p{1}; rep(i,n) p-=(p<<(i+1)); mint res=0; rep(i,k+1) res+=p[i]*F.com(k+n-i,n); cout<<res<<endl; return 0; }
#line 1 "test/yuki2017.test.cpp" #define PROBLEM "https://yukicoder.me/problems/2017" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/yuki2017.test.cpp" #line 1 "type/modint.hpp" template<int Mod> struct ModInt{ int x; ModInt():x(0){} ModInt(int y): x (y >= 0 ? y % Mod : (Mod - (-y) % Mod) % Mod){} ModInt(long long y){ if (y >= 0) { x = (int)(y % (ll)(Mod)); } else { int tmp = (int)((-y) % (ll)Mod); x = (Mod - tmp) % Mod; } } ModInt &operator+=(const ModInt &p){ if((x += p.x) >= Mod) x -= Mod; return *this; } ModInt &operator-=(const ModInt &p){ if((x += Mod - p.x) >= Mod) x -= Mod; return *this; } ModInt &operator*=(const ModInt &p){ x = (int)(1ll * x * p.x % Mod); return *this; } ModInt &operator/=(const ModInt &p){ (*this) *= p.inverse(); return *this; } ModInt operator-()const{return ModInt(-x);} ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;} ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;} ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;} ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;} bool operator==(const ModInt &p)const{return x==p.x;} bool operator!=(const ModInt &p)const{return x!=p.x;} ModInt inverse()const{ int a = x, b = Mod ,u = 1, v = 0, t; while(b>0){ t=a/b; swap(a-=t*b,b);swap(u-=t*v,v); } return ModInt(u); } ModInt pow(long long n)const{ ModInt ret(1),mul(x); while(n>0){ if(n&1) ret*=mul; mul*=mul;n>>=1; } return ret; } friend ostream &operator<<(ostream &os,const ModInt &p){return os<<p.x;} friend istream &operator>>(istream &is,ModInt &a){long long t;is>>t;a=ModInt<Mod>(t);return (is);} static int get_mod(){return Mod;} }; #line 1 "Math/Precalc.hpp" template<typename T> struct Precalc{ vector<T> fact,finv,inv; int Mod; Precalc(int MX):fact(MX),finv(MX),inv(MX),Mod(T::get_mod()){ fact[0]=T(1),fact[1]=T(1),finv[0]=T(1),finv[1]=T(1),inv[1]=T(1); for(int i=2;i<MX;i++){ fact[i]=fact[i-1]*T(i); inv[i]=T(0)-inv[Mod%i]*(T(Mod/i)); finv[i]=finv[i-1]*inv[i]; } } T com(int n,int k){ if(n<k) return T(0); if(n<0 or k<0) return T(0); return fact[n]*(finv[k]*finv[n-k]); } T fac(int n){ return fact[n]; } // 重複組み合わせ:n種類の物から重複を許し,k個選ぶ T nHk(int n,int k){ return com(n+k-1,k); } // 玉n区別,箱k区別,各箱1個以上O(k) T F12_dis_dis_one(int n,int k){ if(n<k)return T(0); T ret=0; for(int i=0;i<=k;i++){ T add=com(k,i)*(T(i).pow(n)); if((k-i)%2) ret-=add; else ret+=add; } return ret; } // 区別できるn人をkチームにわける,チームには最低1人属する // ベン図をイメージ, 包除 // require : T(num).pow(k) T Stirling_number(int n,int k){ T ret=0; for(int i=0;i<=k;i++) ret+=com(k,i)*T(i).pow(n)*((k-i)%2?(-1):1); return ret/T(fac(k)); } // 区別できるn人をkチーム以下にわける T Bell_number(int n,int k){ T ret=0; for(int i=1;i<=k;i++) ret+=Stirling_number(n,i); return ret; } T partition_function(int n,int k){ auto table=partition_function_table(n,k); return table[n][k]; } vector<vector<T>> partition_function_table(int n,int k){ vector<vector<T>> ret(n+1,vector<T>(k+1,0)); ret[0][0]=1; for(int i=0;i<=n;i++)for(int j=1;j<=k;j++)if(i or j){ ret[i][j]=ret[i][j-1]; if(i-j>=0) ret[i][j]+=ret[i-j][j]; } return ret; } // n = y.size - 1 // n次の多項式f, f(0), f(k)の値がわかっていればf(t)が求まる // 1^k + ... n^k はk+1次多項式,k=1ならn(n+1)/2 T LagrangePolynomial(vector<T> y,long long t){ int n=(int)y.size()-1; if(t<=n) return y[t]; T ret=T(0); vector<T> l(n+1,1),r(n+1,1); for(int i=0;i<n;i++) l[i+1]=l[i]*(t-i); for(int i=n;i>0;i--) r[i-1]=r[i]*(t-i); for(int i=0;i<=n;i++){ T add=y[i]*l[i]*r[i]*finv[i]*finv[n-i]; ret+=((n-i)%2?-add:add); } return ret; } /* sum combination(n+x, x), x=l to r https://www.wolframalpha.com/input/?i=sum+combination%28n%2Bx+%2Cx%29%2C+x%3Dl+to+r&lang=ja check n+x < [COM_PRECALC_MAX] */ T sum_of_comb(int n,int l,int r){ if(l>r)return T(0); T ret=T(r+1)*com(n+r+1,r+1)-T(l)*com(l+n,l); ret/=T(n+1); return ret; } /* - sum of comb 2 https://www.wolframalpha.com/input/?i=sum+combination%28i%2Bj%2Ci%29%2C+i%3D0+to+a-1%2C+j%3D0+to+b-1&lang=ja https://yukicoder.me/problems/no/1489 sum binom(i+j,i) i=0 to a-1, j=0 to b-1 = ( binom(a+b,a-1)*(b+1)/a ) - 1 */ // +-1をしてXにたどり着くパターン数 T RandomWalk1D(int X, int N){ X = abs(X); if(X>N or X%2!=N%2) return T(0); return com(N, (N+X)/2); } /* O(1) https://atcoder.jp/contests/abc240/editorial/3423 */ T RandomWalk2D(int X, int Y, int N){ return RandomWalk1D(X+Y, N)*RandomWalk1D(X-Y, N); } }; #line 1 "Math/FormalPowerSeriesNaive.hpp" template<typename T> struct FormalPowerSeriesNaive:vector<T>{ using vector<T>::vector; using P=FormalPowerSeriesNaive; P multiply(const P &lhs,const P &rhs){ auto ret=P((int)lhs.size()+rhs.size()-1); for(int i=0;i<(int)lhs.size();i++)for(int j=0;j<(int)rhs.size();j++) ret[i+j]+=lhs[i]*rhs[j]; return ret; } void shrink(){while(this->size() and this->back()==T(0)) this->pop_back();} P pre(int sz)const{return P(begin(*this),begin(*this)+min((int)this->size(),sz));} P operator+(const P &rhs)const{return P(*this)+=rhs;} P operator+(const T &rhs)const{return P(*this)+=rhs;} P operator-(const P &rhs)const{return P(*this)-=rhs;} P operator-(const T &rhs)const{return P(*this)-=rhs;} P operator*(const P &rhs)const{return P(*this)*=rhs;} P operator*(const T &rhs)const{return P(*this)*=rhs;} P operator/(const P &rhs)const{return P(*this)/=rhs;} P operator%(const P &rhs)const{return P(*this)%=rhs;} P &operator+=(const P &rhs){ if(rhs.size()>this->size()) this->resize(rhs.size()); for(int i=0;i<(int)rhs.size();i++) (*this)[i]+=rhs[i]; return (*this); } P &operator+=(const T &rhs){ if(this->empty()) this->resize(1); (*this)[0]+=rhs; return (*this); } P &operator-=(const P &rhs){ if(rhs.size()>this->size()) this->resize(rhs.size()); for(int i=0;i<(int)rhs.size();i++) (*this)[i]-=rhs[i]; shrink(); return (*this); } P &operator-=(const T &rhs){ if(this->empty()) this->resize(1); (*this)[0]-=rhs; shrink(); return (*this); } P &operator*=(const T &rhs){ const int n=(int)this->size(); for(int i=0;i<n;i++) (*this)[i]*=rhs; return (*this); } P &operator*=(const P &rhs){ if(this->empty() or rhs.empty()){ this->clear(); return (*this); } auto ret=multiply(*this,rhs); (*this)=ret; return (*this); } P &operator%=(const P &rhs){return (*this)-=(*this)/rhs*rhs;} P operator-()const{ P ret(this->size()); for(int i=0;i<(int)this->size();i++) ret[i]=-(*this)[i]; return ret; } P &operator/=(const P &rhs){ if(this->size()<rhs.size()){ this->clear(); return (*this); } int n=(int)this->size()-rhs.size()+1; return (*this)=(rev().pre(n)*rhs.rev().inv(n)); } P operator>>(int sz)const{ if((int)this->size()<=sz) return {}; P ret(*this); ret.erase(ret.begin(),ret.begin()+sz); return ret; } P operator<<(int sz)const{ P ret(*this); ret.insert(ret.begin(),sz,T(0)); return ret; } P rev(int deg=-1)const{ P ret(*this); if(deg!=-1) ret.resize(deg,T(0)); reverse(begin(ret),end(ret)); return ret; } // ref : https://qiita.com/hotman78/items/f0e6d2265badd84d429a P inv(int deg=-1)const{ assert(((*this)[0])!=T(0)); const int n=(int)this->size(); if(deg==-1) deg=n; P ret({T(1)/(*this)[0]}); for(int i=1;i<deg;i<<=1) ret=(ret+ret-ret*ret*pre(i<<1)).pre(i<<1); return ret.pre(deg); } // O(Mult * log k) P pow(ll k,int deg=-1){ if(deg==-1) deg=1000000000; P ret=P{1}; P b(*this); while(k){ if(k&1) ret*=b; b=b*b; k>>=1; if((int)ret.size()>deg) ret.resize(deg); if((int)b.size()>deg) b.resize(deg); } return ret; } // [l,r) k個飛び P slice(int l,int r,int k=1){ P ret; for(int i=l;i<r;i+=k) ret.push_back((*this)[i]); return ret; } /* ref : https://atcoder.jp/contests/aising2020/submissions/15300636 http://q.c.titech.ac.jp/docs/progs/polynomial_division.html order : O(M(d)log(k)) (M(d) -> d次元,multiplyの計算量) return : [x^k] (*this) / q */ T nth_term(P q,ll k){ if(k==0) return (*this)[0]/q[0]; P p(*this); P q_=q; for(int i=1;i<(int)q_.size();i+=2) q_[i]*=-1; q*=q_;p*=q_;// qは奇数項が消える return p.slice(k%2,p.size(),2).nth_term(q.slice(0,q.size(),2),k/2); } /* a_i = sum{j=1}^{d} c_j * a_{i-j} return c */ P berlekamp_massey(){ int N=(int)this->size(); P b={T(-1)},c={T(-1)}; T y=T(1); for(int ed=1;ed<=N;ed++){ int l=(int)c.size(),m=(int)b.size(); T x=0; for(int i=0;i<l;i++) x+=c[i]*(*this)[ed-l+i]; b.emplace_back(0); m++; if(x==T(0)) continue; T freq=x/y; if(l<m){ auto tmp=c; c.insert(begin(c),m-l,T(0)); for(int i=0;i<m;i++) c[m-1-i]-=freq*b[m-1-i]; b=tmp; y=x; }else{ for(int i=0;i<m;i++) c[l-1-i]-=freq*b[m-1-i]; } } reverse(begin(c),end(c)); return c; } // this[0], this[1] ... // linear recurrence // -> return Nth term // verified : https://atcoder.jp/contests/kupc2021/submissions/26974136 T nth_linear_recurrence(long long N){ auto q=berlekamp_massey(); assert(not q.empty() and q[0]!=T(0)); if(N<(int)this->size()) return (*this)[N]; auto p=this->pre((int)q.size()-1)*q; p.resize((int)q.size()-1); return p.nth_term(q,N); } }; #line 8 "test/yuki2017.test.cpp" using mint=ModInt<1000000007>; Precalc<mint> F(500000); using FPS=FormalPowerSeriesNaive<mint>; signed main(){ int n,k;cin>>n>>k; rep(i,n){int a;cin>>a;} FPS p{1}; rep(i,n) p-=(p<<(i+1)); mint res=0; rep(i,k+1) res+=p[i]*F.com(k+n-i,n); cout<<res<<endl; return 0; }