fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #define MOD 1000000007
  3. using namespace std;
  4.  
  5. typedef long long int LL;
  6. pair<LL,LL> block[1005];
  7. LL ans[1005],fact[200005];
  8.  
  9. LL powmod(LL b,LL p)
  10. {
  11.     if(p==0)
  12.         return 1;
  13.     LL ans=powmod(b,p/2);
  14.     ans=(ans*ans)%MOD;
  15.     if(p%2==0)
  16.         return ans;
  17.     else
  18.     {
  19.         ans=(ans*b)%MOD;
  20.         return ans;
  21.     }
  22. }
  23.  
  24. LL F(LL a,LL b,LL c,LL d)
  25. {
  26.     LL x=c-a;
  27.     LL y=d-b;
  28.     LL res=fact[x+y];
  29.     LL deno=(fact[x]*fact[y])%MOD;
  30.     res=res*powmod(deno,MOD-2);
  31.     res=res%MOD;
  32.     return res;
  33. }
  34.  
  35. int main()
  36. {
  37.    // freopen("input.txt","r",stdin);
  38.     LL t,m,n,p,x,y;
  39.     fact[0]=1;
  40.     for(LL i=1;i<=200005;i++)
  41.     {
  42.         fact[i]=(fact[i-1]*i)%MOD;
  43.     }
  44.  
  45.     scanf("%lld",&t);
  46.     while(t--)
  47.     {
  48.         scanf("%lld %lld %lld",&m,&n,&p);
  49.     for(int i=0;i<p;i++)
  50.     {
  51.         scanf("%lld %lld",&x,&y);
  52.         block[i]=make_pair(x,y);
  53.     }
  54.     block[p]=make_pair(m,n);
  55.     sort(block,block+p+1);
  56.  
  57.     for(int i=0;i<=p;i++)
  58.     {
  59.         ans[i]=F(1,1,block[i].first,block[i].second);
  60.     }
  61.     for(int i=0;i<p;i++)
  62.     {
  63.         for(int j=i+1;j<p+1;j++)
  64.         {
  65.             if((block[j].first<block[i].first)||(block[j].second<block[i].second))
  66.                 continue;
  67.             ans[j]=(ans[j]-(ans[i]*F(block[i].first,block[i].second,block[j].first,block[j].second))%MOD+MOD)%MOD;
  68.         }
  69.     }
  70.     if(ans[p]<0)
  71.         ans[p]+=MOD;
  72.     printf("%lld\n",ans[p]);
  73.     }
  74.     return 0;
  75. }
Success #stdin #stdout 0s 4320KB
comments (?)
stdin
copy 
2
3 2 0
2 3 1
1 2
stdout
copy 
3
1
https://ideone.com/Eow0jb
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!