fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <map>
  4. #include <math.h>
  5.  
  6. #include <string>
  7. #include <algorithm>
  8. typedef long long ull;
  9. typedef long long int lli;
  10. const int M=1000000007;
  11. using namespace std;
  12. map<string,ull> htable;
  13. map<lli,string> binarys;
  14. map<lli,int> binaryc;
  15.  
  16. int aehash(string s)
  17. {
  18.     if(htable.count(s)>0)
  19. 		return htable[s];
  20.  
  21. 	string temp = s;
  22. 	while(temp.find('E')!=-1)
  23. 		temp.replace(temp.find('E'),1,"");
  24. 	ull result=temp.length();
  25.  
  26. 	if(s.length()>1)
  27. 	{
  28. 		string s1 = s.substr(0,s.length()/2);
  29. 		string s2 = s.substr(s.length()/2,s.length());
  30. 		result +=max(aehash(s1),aehash(s2));
  31. 	}
  32. 	htable[s]=result;
  33. 	return result;
  34. }
  35.  
  36. int toBinary(lli i,int bit)
  37. {
  38. 	if(binarys.count(i)!=0)
  39. 	{
  40. 		return binaryc[i];
  41. 	}
  42.  
  43. 	lli temp=i;
  44. 	string s(bit,'A');
  45. 	int ecount=0;
  46. 	do
  47. 	{
  48. 		bit--;
  49. 		if(i%2==1)
  50. 		{
  51. 			ecount++;
  52. 			s[bit]='E';
  53. 		}
  54. 	}while((i/=2)!=0);
  55. 	binarys[temp]=s;
  56. 	binaryc[temp]=ecount;
  57. 	return ecount;
  58. }
  59.  
  60. int main()
  61. {
  62.  
  63. 	map<int,ull> count;
  64.  
  65. 	int t,a,e,v;
  66.  
  67. 	scanf("%d",&t);
  68.  
  69. 	while(t--)
  70. 	{
  71. 		count.clear();
  72. 		binarys.clear();
  73. 		binaryc.clear();
  74. 		scanf("%d%d%d",&a,&e,&v);
  75.  
  76. 		for(lli i=0;i<pow(2,a+e);i++)
  77. 		{
  78. 			if( binaryc.count(i)==0 )
  79. 				if(toBinary(i,a+e)==e)
  80. 				{
  81. 					if(htable.count(binarys[i])==0)
  82. 						htable[binarys[i]]=aehash(binarys[i]);
  83. 					count[htable[binarys[i]]]++;
  84. 				}
  85. 			else continue;
  86. 		}
  87. 		count[v]%=M;
  88. 		printf("%llu\n",count[v]);
  89. 	}
  90. 	htable.clear();
  91. 	binaryc.clear();
  92. 	binarys.clear();
  93. 	count.clear();
  94. 	return 0;
  95. }
Success #stdin #stdout 0.02s 2832KB
comments (?)
stdin
copy 
4
0 0 0
1 0 1
3 2 6
4 2 8
stdout
copy 
1
0
0
0
https://ideone.com/PwVE5Q
language:
C++ (gcc 8.3)
created:
12 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!