fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int mod=1e9+7;
  5. ll exponentiation(ll base,ll power)
  6. {
  7.     ll ans=1;
  8.     while(power>0)
  9.     {
  10.        if(power%2==1)
  11.             ans=(ans*base)%mod;
  12.        base=(base*base)%mod;
  13.        power/=2;
  14.     }
  15.     return ans%mod;
  16. }
  17.  
  18. ll inverse_mod(ll exp,ll base){ return (exp%mod*(exponentiation(base,mod-2))%mod)%mod; }
  19. ll factorial[1000100];
  20. ll binomial(ll a,ll b)
  21. {
  22.     ll top=factorial[a];
  23.     ll below=factorial[b];
  24.     below=(below*factorial[a-b])%mod;
  25.     ll ans=inverse_mod(top,below);
  26.     return ans;
  27. }
  28.  
  29. int main()
  30. {
  31.     factorial[0]=factorial[1]=1;
  32.     for(ll i=2;i<1000100;i++)
  33.         factorial[i]=(i*factorial[i-1])%mod;
  34.     long long int ans=0,t,x1,x2,y1,y2;
  35.     cin>>t;
  36.     for(int j=1;j<=t;j++)
  37.     {
  38.         ans=0;
  39.         cin>>x1>>y1>>x2>>y2;
  40.         for(int i=0;i<=min(x2-x1,y2-y1);i++)
  41.         {
  42.             ll firstpart=(binomial(x2-x1+y2-y1-2*i,y2-y1-i));
  43.             ll secondpart=binomial(x2-x1+y2-y1-i,i);
  44.             ll temp=(firstpart*secondpart*1LL)%mod;
  45.             ans=(ans+temp)%mod;
  46.         }
  47.         cout<<"Case "<<j<<": "<<ans<<endl;
  48.     }
  49. return 0;
  50. }
  51.  
Success #stdin #stdout 0s 23056KB
comments (?)
stdin
copy 
3

1 2 2 3

2 2 3 3

3 4 3 5
stdout
copy 
Case 1: 3
Case 2: 3
Case 3: 1
https://ideone.com/G1GwQq
language:
C++14 (clang 8.0)
created:
7 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!