fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long int ll;
  5. ll mod = 1e9+7;
  6. ll fac[1009],inverse[1009];
  7. void factorial(){
  8. 	fac[0]=fac[1]=1;
  9. 	for(int i =2;i<=1000;i++){
  10. 		fac[i]= (fac[i-1]*i)%mod;
  11. 	}
  12. }
  13.  
  14. ll power(ll a,ll b){
  15.     if(b==0)return 1;
  16.     ll ans = 1;
  17.     if(b%2==1)ans = (ans%mod * a%mod)%mod;
  18.     ll t = power(a,b/2)%mod;
  19.     return (ans * (t%mod * t%mod)%mod)%mod;
  20. }
  21.  
  22.  void inv(){
  23. 	for(int i = 0;i<=1000;i++){
  24. 		inverse[i] = power(fac[i],mod-2);
  25. 	}
  26. }
  27. ll nck(int n,int k){
  28. 	ll a = fac[n]%mod;
  29. 	ll b = power(fac[k],mod-2)%mod;
  30. 	ll c = power(fac[n-k],mod-2)%mod;
  31. 	return (((a * b)%mod) * c)%mod;
  32. }
  33.  
  34. ll npk(int n,int k){
  35. 	ll a = fac[n]%mod;
  36. 	ll b = inverse[n-k]%mod;
  37. 	return (a*b)%mod;
  38.  
  39. }
  40. int main(){
  41. 	int t;
  42. 	cin>>t;
  43. 	int Case = 0;
  44. 	factorial();
  45. 	inv();
  46. 	while(t--){
  47. 		Case++;
  48. 		int x,y;
  49. 		cin>>x>>y;
  50. 		vector<ll> a(x+1);
  51. 		for(int i = 1 ; i <=x ;i++){
  52. 			a[i] = nck(x,i);
  53. 		}
  54. 		a[0]=1;
  55. 		vector<ll> b(y+1);
  56. 		for(int i = 1 ;i<=y ;i++){
  57. 			b[i]=nck(y,i);
  58. 		}
  59. 		b[0]=1;
  60. 		ll injective = 0;
  61. 		for(int i = 1;i<=x;i++){
  62. 			ll ti = 0;
  63.  
  64. 			for(int j = i+1;j<=y;j++){
  65. 				ti = (ti + ( (npk(j,i)) * (b[j]) )%mod)%mod;
  66. 			}
  67. 			injective = (injective + (ti * a[i])%mod)%mod;
  68. 		}
  69. 		long long subjective = 0;
  70. 		for(int i = 1;i<=y;i++){
  71. 			ll ti = 0;
  72. 			ll w = fac[i];
  73. 			for(int j = i+1;j<=x;j++){
  74. 				ti = ti + (( ((a[j] * w)%mod) * power(i,j-i))%mod);
  75. 			}
  76. 			subjective = (subjective + ((ti * b[i])%mod))%mod;
  77. 		}
  78.  
  79. 		long long bijective = 0;
  80. 		for(int i = 1 ; i<=min(x,y);i++ ){
  81. 			bijective = (bijective + ( ( ((a[i]%mod)*(b[i]%mod))%mod )*(fac[i]%mod))%mod )%mod;
  82. 		}
  83. 		long long tot = 0;
  84. 		for(int i = 1; i <= x ; i++){
  85. 			for(int j= 1;j <=y; j++){
  86. 				tot = (tot + (((power(j,i)*a[i])%mod)*b[j])%mod)%mod;
  87. 			}
  88. 		}
  89. 		cout<<"Case "<<Case<<": ";
  90. 		cout<<(injective%mod+bijective%mod)%mod<<" "<<(subjective%mod+bijective%mod)%mod<<" "<<
  91. 				(bijective)%mod<<" "<<tot%mod<<'\n';
  92.  
  93. 	}
  94.  
  95.  
  96. }
  97.  
Success #stdin #stdout 0s 4448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DWHlAD
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!