fork download
copy 
  1. //Bismillahir Rahmanir Rahim
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll long long
  7. #define gcd(a,b) __gcd(a,b)
  8. #define endl '\n'
  9. const int N=2e5+10;
  10. const int inf=1e9;
  11. //const int mod=1000000007;
  12.  
  13. vector<int>num;
  14. ll dp[60][(1<<10)+2][2][2];
  15. int n;
  16. int base;
  17. string s;
  18.  
  19. ll call(int pos, int mask, int is_start, int nf, int flag){
  20.  
  21.     if(pos==n){
  22. 		if(mask==0)
  23. 			return 0LL;
  24. 		bool chk=true;
  25. 		string tmp;
  26. 		if(flag)
  27. 		{
  28. 			if(s[0]=='N')
  29. 				chk=false;
  30. 		}
  31.  
  32.  
  33.         for(int i=1; i<=base; i++)
  34. 		{
  35. 			if(mask & (1<<(i-1)))
  36. 			{
  37. 				if(s[i]=='N')
  38. 					chk=false;
  39. 			}				
  40. 		}
  41.  
  42.  
  43. 		if(chk)
  44. 		{
  45. 			return 1LL;
  46. 		}
  47. 		else
  48. 		{
  49. 			return 0LL;
  50. 		}
  51.  
  52.     }
  53.  
  54.     if(dp[pos][mask][is_start][nf] != -1)return dp[pos][mask][is_start][nf];
  55.  
  56.     ll res = 0;
  57.  
  58.     int LMT=nf;
  59.  
  60. 	if(nf)
  61. 		LMT=base-1;
  62. 	else
  63. 	{
  64. 		LMT=num[pos];
  65. 	}
  66.  
  67.  
  68. 	if(is_start==0)
  69. 	{
  70. 		for(int dgt=0; dgt<=LMT; dgt++)
  71. 		{
  72. 			int f=nf;
  73. 			if(dgt < LMT) f = 1; 
  74.  
  75. 			if(dgt==0)
  76. 			{
  77. 				res+=call(pos+1, mask, 0, f, 1);
  78. 			}
  79. 			else
  80. 			{
  81. 				res+=call(pos+1, mask|(1<<(dgt-1)), 0, f, 0);
  82. 			}
  83. 		}
  84. 	}
  85. 	else
  86. 	{
  87. 		for(int dgt=1; dgt<=LMT; dgt++)
  88. 		{
  89. 			int f=nf;
  90. 			if(dgt < LMT) f = 1; 
  91.  
  92. 			res+=call(pos+1, mask|(1<<(dgt-1)), 0, f, 0);
  93. 		}
  94. 		res+=call(pos+1, 0, 1, 1, 0);
  95. 	}
  96.  
  97. 	return dp[pos][mask][is_start][nf]=res;
  98. }
  99.  
  100. ll solve(ll tmp){
  101.     num.clear();
  102.  
  103. 	while(tmp)
  104. 	{
  105. 		num.push_back(tmp%base);
  106. 		tmp/=base;
  107. 	}
  108.  
  109. 	n=num.size();
  110.  
  111. 	reverse(num.begin(), num.end());
  112. 	memset(dp, -1, sizeof(dp));
  113.  
  114.     ll res = call(0, 0, 1, 0, 0);
  115.     return res;
  116. }
  117.  
  118. int  main(int argc, char const *argv[])
  119. {
  120. 	/*#ifndef ONLINE_JUDGE
  121. 		freopen("input.txt","r",stdin);
  122. 		freopen("output.txt","w",stdout);
  123. 	#endif*/
  124. 	ios_base::sync_with_stdio(false);
  125. 	cin.tie(NULL);
  126. 	cout.tie(0);
  127.  
  128. 	while(1)
  129. 	{
  130. 		ll a, b;
  131. 		cin >> a >> b;
  132.  
  133. 		cin >> base >> s;
  134.  
  135. 		if(a==-1 && b==-1)
  136. 			break;
  137.  
  138.  
  139. 		ll ans=solve(b)-solve(a-1);
  140.  
  141.  
  142. 		cout << ans << endl;
  143. 	}	
  144.  
  145. 	//fprintf(stderr, "Time: %d ms\n", (int)(clock()*1000.0/CLOCKS_PER_SEC));
  146.  
  147. 	return 0;
  148. }
Success #stdin #stdout 0.01s 5604KB
comments (?)
stdin
copy 
1 10 3 SNS
99 999 5 NSSNS
1110 1111 10 NSNNNNNNNN
1 10000000000000000 10 NNNNNSNNNN
1 10000000000000000 7 SSSSSSS
-1 -1 -1 *
stdout
copy 
3
300
1
32768
10000000000000000
https://ideone.com/IHsTfK
language:
C++14 (gcc 8.3)
created:
3 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!