This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397" #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../linearalgebra/squarematrix.cpp" #include "../../mod/mint.cpp" #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); const int MAX = 80; const int MOD = 1e9+9; using M = Mint<int, MOD>; using SM = SquareMatrix<M, MAX>; using ll = long long; ll w,h,n; ll cnt=0; while(cin>>w>>h>>n,w){ vector<ll> x(n),y(n); for(int i=0;i<n;i++) cin>>x[i]>>y[i]; { using P = pair<ll, ll>; vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(y[i],x[i]); sort(vp.begin(),vp.end()); for(int i=0;i<n;i++) tie(y[i],x[i])=vp[i]; } SM b; for(int i=0;i<w;i++){ b[i][i]=M(1); if(i-1>=0) b[i][i-1]=M(1); if(i+1<w) b[i][i+1]=M(1); } ll d=1; SM res=SM::mul_identity(); for(int k=0;k<n;k++){ if(y[k]==d) continue; res=b.pow(y[k]-d-1)*res; int j=k; SM c(b); while(j<n&&y[k]==y[j]){ for(int i=0;i<w;i++) c[x[j]-1][i]=0; j++; } res=c*res; d=y[k]; } res=b.pow(h-d)*res; cout<<"Case "<<++cnt<<": "<<res[w-1][0].v<<endl; } return 0; }
#line 1 "test/aoj/2397.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397" #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "linearalgebra/squarematrix.cpp" #line 3 "linearalgebra/squarematrix.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename R, size_t N> struct SquareMatrix{ typedef array<R, N> arr; typedef array<arr, N> mat; mat dat; SquareMatrix(){ for(size_t i=0;i<N;i++) for(size_t j=0;j<N;j++) dat[i][j]=R::add_identity(); } bool operator==(const SquareMatrix& a) const{ return dat==a.dat; } size_t size() const{return N;} arr& operator[](size_t k){return dat[k];} const arr& operator[](size_t k) const {return dat[k];} static SquareMatrix add_identity(){return SquareMatrix();} static SquareMatrix mul_identity(){ SquareMatrix res; for(size_t i=0;i<N;i++) res[i][i]=R::mul_identity(); return res; } SquareMatrix operator*(const SquareMatrix &B) const{ SquareMatrix res; for(size_t i=0;i<N;i++) for(size_t j=0;j<N;j++) for(size_t k=0;k<N;k++) res[i][j]=res[i][j]+(dat[i][k]*B[k][j]); return res; } SquareMatrix operator+(const SquareMatrix &B) const{ SquareMatrix res; for(size_t i=0;i<N;i++) for(size_t j=0;j<N;j++) res[i][j]=dat[i][j]+B[i][j]; return res; } SquareMatrix pow(long long n) const{ SquareMatrix a=*this,res=mul_identity(); while(n){ if(n&1) res=res*a; a=a*a; n>>=1; } return res; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "mod/mint.cpp" #line 3 "mod/mint.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T, T MOD = 1000000007> struct Mint{ inline static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;} Mint operator-(Mint a) const{return Mint(v)-=a;} Mint operator*(Mint a) const{return Mint(v)*=a;} Mint operator/(Mint a) const{return Mint(v)/=a;} Mint operator+() const{return *this;} Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} static Mint comb(long long n,int k){ Mint num(1),dom(1); for(int i=0;i<k;i++){ num*=Mint(n-i); dom*=Mint(i+1); } return num/dom; } }; template<typename T, T MOD> ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;} //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 9 "test/aoj/2397.test.cpp" #undef call_from_test #ifdef SANITIZE #define IGNORE #endif signed main(){ cin.tie(0); ios::sync_with_stdio(0); const int MAX = 80; const int MOD = 1e9+9; using M = Mint<int, MOD>; using SM = SquareMatrix<M, MAX>; using ll = long long; ll w,h,n; ll cnt=0; while(cin>>w>>h>>n,w){ vector<ll> x(n),y(n); for(int i=0;i<n;i++) cin>>x[i]>>y[i]; { using P = pair<ll, ll>; vector<P> vp; for(int i=0;i<n;i++) vp.emplace_back(y[i],x[i]); sort(vp.begin(),vp.end()); for(int i=0;i<n;i++) tie(y[i],x[i])=vp[i]; } SM b; for(int i=0;i<w;i++){ b[i][i]=M(1); if(i-1>=0) b[i][i-1]=M(1); if(i+1<w) b[i][i+1]=M(1); } ll d=1; SM res=SM::mul_identity(); for(int k=0;k<n;k++){ if(y[k]==d) continue; res=b.pow(y[k]-d-1)*res; int j=k; SM c(b); while(j<n&&y[k]==y[j]){ for(int i=0;i<w;i++) c[x[j]-1][i]=0; j++; } res=c*res; d=y[k]; } res=b.pow(h-d)*res; cout<<"Case "<<++cnt<<": "<<res[w-1][0].v<<endl; } return 0; }