fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define si(x) scanf("%d",&x)
  6. #define sll(x) scanf("%lld",&x)
  7. #define pri(x) printf("%d",x)
  8. #define pll(x) printf("%lld",x)
  9. #define sstr(s) scanf("%s",s)
  10. #define nl printf("\n")
  11. #define ll long long int
  12. #define pii pair<int,int>
  13. #define pLL pair<ll,ll>
  14. #define vi vector<int>
  15. #define pb push_back
  16. #define mp make_pair
  17. #define fr first
  18. #define se second
  19. #define SZ 100005
  20. #define FOR(i,x,y) for(int i=x;i<y;i++)
  21. #define mod 1000000007
  22.  
  23. ll fact[200005];
  24. ll invfact[200005];
  25.  
  26. ll power(ll a, ll b) {
  27.     ll ans = 1;
  28.     while(b) {
  29. 	if(b&1) {
  30. 	    ans = (ans*a)%mod;
  31. 	}
  32. 	a = (a*a)%mod;
  33. 	b = b>>1;
  34.     }
  35.     return ans;
  36. }
  37.  
  38. void func() {
  39.     fact[0] = fact[1] = 1;
  40.     invfact[0] = invfact[1] = 1;
  41.     for(int i=2;i<=200000;i++) {
  42. 	fact[i] = (1ll*fact[i-1]*i)%mod;
  43. 	invfact[i] = (1ll*invfact[i-1]*power(i,mod-2))%mod;
  44.     }
  45. }
  46.  
  47. ll answer(int x1, int y1, int x2, int y2) {
  48.     ll m = x2-x1;
  49.     ll n = y2-y1;
  50.     ll k = min(m,n);
  51.     ll ans = 0;
  52.     for(int i=0;i<=k;i++) {
  53. 	ll t1 = (1ll*invfact[i]*invfact[n-i])%mod;
  54. 	t1 = (1ll*t1*invfact[m-i])%mod;
  55. 	ans = ans + (1ll*fact[n+m-i]*t1)%mod;
  56. 	ans %= mod;
  57.     }
  58.     return ans;
  59. }
  60.  
  61. int main()
  62. {
  63.     func();
  64.     int t; si(t);
  65.     int tc=1;
  66.     while(t--) {
  67. 	int x1,y1,x2,y2;
  68. 	cin>>x1>>y1>>x2>>y2;
  69. 	if(x1>x2 || y1>y2) {
  70. 	    cout<<"Case "<<tc++<<": "<<0<<endl;
  71. 	    continue;
  72. 	}
  73. 	cout<<"Case "<<tc++<<": "<<answer(x1,y1,x2,y2)<<endl;
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0.1s 5872KB
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/ooCagR
problem LVADER, based on SPOJ submission 19169824 (C++ 4.3.2), 2017-04-07 07:30:42
language:
C++ 4.3.2 (gcc-4.3.2)
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!