fork download 
  1. #include <stdio.h>
  2.  
  3. #define    ll long long
  4. #define	MOD	1000000007
  5.  
  6. ll fact[800001], fact_inv[800001];
  7.  
  8. ll modPow(ll a, ll x, ll p)
  9. {
  10. 	ll res = 1;
  11. 	while (x > 0ll) {
  12. 		if (x % 2 != 0) {
  13. 			res = (res * a) % p;
  14. 		}
  15. 		a = (a * a) % p;
  16. 		x /= 2;
  17. 	}
  18.  
  19. 	return res;
  20. }
  21.  
  22. ll modInverse(ll a, ll p) {
  23. 	return modPow(a, p-2, p);
  24. }
  25.  
  26. ll comb(int a,int b){
  27.   return (((fact[a] * fact_inv[b]) % MOD) * fact_inv[a-b]) % MOD;
  28. }
  29.  
  30. ll ways(int a, int b){
  31.   return comb(a+b, a);
  32. }
  33.  
  34. inline void scan(int *a) {
  35. 	register char c=0;
  36. 	while (c < 33)
  37. 		c = getchar_unlocked();
  38. 	*a = 0;	
  39. 	while (c > 33) {
  40. 		*a = *a * 10 + c - '0';
  41. 		c = getchar_unlocked();
  42. 	}
  43. }
  44.  
  45. main()
  46. {
  47. 	int i;
  48. 	fact[0] = fact[1] = fact_inv[0] = fact_inv[1] = 1;
  49. 	for (i = 2; i <= 800000; i++) {
  50. 		fact[i] = (i * fact[i-1]) % MOD;
  51. 		fact_inv[i] = modInverse(fact[i], MOD);
  52. 	}
  53. 	int N, M, A, B;
  54. 	int p;
  55. 	int t;
  56. 	ll result;
  57. 	scan(&t);
  58. 	while(t--) {
  59. 		scan(&N);
  60. 		scan(&M);
  61. 		scan(&A);
  62. 		scan(&B);
  63. 		result = 0;
  64. 		for (p = 0; p <= N-A; p++)
  65. 			result += ways(p, B-1) * ways(N-p, M-B);
  66.  
  67. 		printf("%lld\n", result);
  68. 	}
  69.  
  70. 	return 0;
  71. }
Success #stdin #stdout 1.48s 15184KB
comments (?)
stdin 
1
1000 1000 500 500
stdout 
-3205230452950140774
https://ideone.com/uhZNCo
language:
C++ (gcc 8.3)
created:
12 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!