fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. typedef pair<int,int> pii;
  6. typedef pair<ll,ll> pll;
  7. typedef pair<ull,ull> pull;
  8. #define mod 1000000007
  9. #define sci(n) scanf("%d",&n)
  10. #define scli(n) scanf("%I32d",&n)
  11. #define sclli(n) scanf("%I64d",&n)
  12. #define pfi(n) printf("%d",n)
  13. #define pfli(n) printf("%I32d",n)
  14. #define pflli(n) printf("%I64d",n)
  15. #define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
  16. #define reprev(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
  17. #define mp make_pair
  18. #define f first
  19. #define s second
  20. #define sync ios_base::sync_with_stdio(false)
  21. vector<pll> bl;
  22. ll fact[200005];
  23. ll ifact[200005];
  24.  
  25. long long invert_mod(long long a,long long p) {
  26.     long long n = 1, old = 0, q = p, r, h;
  27.     bool pos = false;
  28.     while (a > 0) {
  29.         r = q%a;
  30.         q = q/a;
  31.         h = q*n + old;
  32.         old = n;
  33.         n = h;
  34.         q = a;
  35.         a = r;
  36.         pos = !pos;
  37.     }
  38.     return pos ? old : (p - old);
  39. }
  40. void calc_fact()
  41. {
  42.     fact[0]=fact[1]=1;
  43.     ifact[0]=ifact[1]=1;
  44.     for(ll i=2;i<200005;i++)
  45.        { fact[i] = (i*fact[i-1])%mod;
  46.          ifact[i] = invert_mod(fact[i],mod);//*ifact[i-1];
  47.         }
  48. }
  49. int main(void)
  50. {   sync;
  51.     //cout<<"hi";
  52.     ll h,w,n;
  53.     cin>>h>>w>>n;
  54.     calc_fact();
  55.     bl.resize(n);
  56.     for(int i=0;i<n;i++)
  57.     {
  58.         cin>>bl[i].f>>bl[i].s;
  59.     }
  60.     bl.push_back(mp(h,w));
  61.     vector <ll> dp(n+1,0);
  62.     sort(bl.begin(),bl.end());
  63.     dp[0] = ((fact[bl[0].f + bl[0].s-2]*ifact[bl[0].f-1])%mod*ifact[bl[0].s-1])%mod;
  64.     //cout<<dp[0]<<"\n";
  65.    // ull ans = 0;
  66.     for(int i=1;i<=n;i++)
  67.         {
  68.             //ll x = bl[i].f,y=bl[i].s;
  69.             dp[i] = ((fact[bl[i].f + bl[i].s-2]*ifact[bl[i].f-1])%mod*ifact[bl[i].s-1])%mod;
  70.             //cout<<dp[i]<<"\n";
  71.  
  72.             ll ans=0;
  73.             for(int j=0;j<i;j++)
  74.             {    //int j = i-1;
  75.                ll val = ( ( fact[(bl[i].f + bl[i].s)-(bl[j].f+bl[j].s)]*ifact[bl[i].f-bl[j].f])%mod *ifact[bl[i].s-bl[j].s])%mod;
  76.                 ans = (ans + (dp[j]*val)%mod)%mod;
  77.             //    cout<<"Val: "<<val<<"Ans: "<<ans<<"\n";
  78.                 //ans =  (ans +( )%mod;
  79.                 }
  80.             dp[i] = ( dp[i] + (mod - ans))%mod;
  81.             //cout<<dp[i]<<"\n";
  82.         }
  83.         cout<<dp[n];
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.23s 6408KB
comments (?)
stdin
copy 
100 100 4
1 2
2 3
3 4
4 5
stdout
copy 
892239589
https://ideone.com/NURs5H
language:
C++14 (gcc 8.3)
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!