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. ll mulmod(ll a,ll b){
  14. 	return ( (a%mod) * (b%mod) )%mod;
  15. }
  16. ll plusmod(ll a,ll b){
  17. 	return ( (a%mod) + (b%mod) )%mod;
  18. }
  19.  
  20. ll power(ll a,ll b){
  21.     if(b==0)return 1;
  22.     ll ans = 1;
  23.     if(b%2==1)ans = (ans%mod * a%mod)%mod;
  24.     ll t = power(a,b/2)%mod;
  25.     return (ans * (t%mod * t%mod)%mod)%mod;
  26. }
  27.  
  28.  void inv(){
  29. 	inverse[0] = inverse[1] = 1;
  30. 	for(int i = 2;i<=1000;i++){
  31. 		inverse[i] = mulmod(inverse[i-1], power(i,mod-2));
  32. 	}
  33. }
  34. ll nck(int n,int k){
  35. 	ll a = fac[n]%mod;
  36. 	ll b = inverse[k];
  37. 	ll c = inverse[n-k];
  38. 	return mulmod( mulmod(a,b),c);
  39. }
  40.  
  41. ll npk(int n,int k){
  42. 	ll a = fac[n];
  43. 	ll b = inverse[n-k];
  44. 	return mulmod(a,b);
  45.  
  46. }
  47.  
  48. int main(){
  49. 	int t;
  50. 	cin>>t;
  51. 	int Case = 0;
  52. 	factorial();
  53. 	inv();
  54. 	while(t--){
  55. 		Case++;
  56. 		int x,y;
  57. 		cin>>x>>y;
  58. 		vector<ll> xck(x+1);
  59. 		for(int i = 1 ; i <=x ;i++){
  60. 			xck[i] = nck(x,i);
  61. 		}
  62. 		xck[0]=1;
  63. 		vector<ll> yck(y+1);
  64. 		for(int i = 1 ;i<=y ;i++){
  65. 			yck[i]=nck(y,i);
  66. 		}
  67. 		yck[0]=1;
  68. 		ll injective = 0;
  69. 		for(int i = 1;i<=x;i++){
  70. 			ll temp = 0;
  71. 			for(int j = i+1;j<=y;j++){
  72. 				temp = plusmod( temp, mulmod(npk(j,i),yck[j]) );
  73. 			}
  74. 			injective = plusmod(injective, mulmod(temp, xck[i]) );
  75. 		}
  76. 		long long subjective = 0;
  77. 		for(int i = 1;i<=y;i++)
  78. 		{
  79. 			ll temp = 0;
  80. 			ll w = fac[i];
  81. 			for(int j = i+1;j<=x;j++){
  82. 				temp = plusmod(temp, mulmod(mulmod(xck[j],w), power(i,j-i) ) );
  83. 			}
  84. 			subjective = plusmod(subjective, mulmod(temp,yck[i]) );
  85. 		}
  86.  
  87. 		long long bijective = 0;
  88. 		for(int i = 1 ; i<=min(x,y);i++ ){
  89. 			bijective = plusmod(bijective, mulmod( mulmod(xck[i],yck[i]), fac[i] ) );
  90. 		}
  91.  
  92. 		long long tot = 0;
  93. 		for(int i = 1; i <= x ; i++){
  94. 			for(int j= 1;j <=y; j++){
  95. 				tot = plusmod(tot, mulmod( mulmod(xck[i],power(j,i)), yck[j]) );
  96. 			}
  97. 		}
  98. 		cout<<"Case "<<Case<<": ";
  99. 		cout<<plusmod(injective,bijective)<<" "<<plusmod(subjective,bijective)<<" "<<
  100. 				bijective<<" "<<tot<<'\n';
  101.  
  102. 	}
  103.  
  104.  
  105. }
  106.  
Success #stdin #stdout 0s 4268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Hxju1m
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!