[入门OJ3876]怎样学习哲学

题目大意：
　　有一个$n\times m(n,m\leq 10^9)$的网格图，从一个点可以到下一行中列数比它大的点。有$k(k\leq 2000)$个点是不能走的，问从第$1$行到第$n$行共有几种方案。

思路：
　　动态规划求出以点$i$为终点的方案数，直接$O(nm)$推显然会超时，因此我们$O(k)$可以对于每个障碍点求出组合数。组合数可以用Lucas定理求。
　　Lucas定理：$\binom{n}{m}\mod p=\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\mod p}{m\mod p}\mod p$。

 #include<cstdio>

 #include<cctype>

 #include<vector>

 #include<algorithm>

 typedef long long int64;

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int mod=,K=;

 int fact[mod],factinv[mod],f[K];

 std::pair<int,int> v[K];

 void exgcd(const int &a,const int &b,int &x,int &y) {

     if(!b) {

         x=;

         y=;

         return;

     }

     exgcd(b,a%b,y,x);

     y-=a/b*x;

 }

 inline int inv(const int &x) {

     int ret,tmp;

     exgcd(x,mod,ret,tmp);

     return (ret%mod+mod)%mod;

 }

 int lucas(const int &n,const int &m) {

     if(n<m) return ;

     if(n<mod&&m<mod) return (int64)fact[n]*factinv[m]%mod*factinv[n-m]%mod;

     return (int64)lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod;

 }

 int main() {

     fact[]=;

     for(register int i=;i<mod;i++) {

         fact[i]=(int64)fact[i-]*i%mod;

     }

     factinv[mod-]=inv(fact[mod-]);

     for(register int i=mod-;~i;i--) {

         factinv[i]=(int64)factinv[i+]*(i+)%mod;

     }

     const int n=getint(),m=getint(),k=getint();

     for(register int i=;i<k;i++) {

         const int x=getint(),y=getint();

         v[i]=std::make_pair(x,y);

     }

     std::sort(&v[],&v[k]);

     v[k]=std::make_pair(n+,m+);

     for(register int i=;i<=k;i++) {

         f[i]=lucas(v[i].second-,v[i].first-);

         for(register int j=;j<i;j++) {

             if(v[i].first<=v[j].first||v[i].second<=v[j].second) continue;

             f[i]=((f[i]-(int64)f[j]*lucas(v[i].second-v[j].second-,v[i].first-v[j].first-))%mod+mod)%mod;

         }

     }

     printf("%d\n",f[k]);

     return ;

 }

巴特西

[入门OJ3876]怎样学习哲学

最新文章

热门文章