fork(1) download
  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
stdin
4
0 0 0
1 0 1
3 2 6
4 2 8
stdout
1
0
0
0