fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4.  
  5. LL toint(string s, int n){
  6. //	cout<<s<"\n";
  7. 	int res = 0;
  8. 	int j = 0;
  9. 	for(int i=n-1; i>=0;i--, j++){
  10. 		if(s[i]=='1'){
  11. 			res+=pow(2,j);
  12. 		}
  13. //		j++
  14. 	}
  15. //	cout<<res<<"\n";
  16. 	return res;
  17. }
  18.  
  19. LL solve(string &s, int i, int m, int n){
  20. 	if(i==n){
  21. //		cout<<s<<"\n";
  22. 		if(toint(s,n)%m!=0) return 0;
  23. 		return 1;
  24. 	}
  25. 	else{
  26. 		if(s[i]!='_') return solve(s,i+1,m,n);
  27. 		else{
  28. 			s[i] = '1';
  29. 			LL left = solve(s, i+1, m, n);
  30. 			s[i] = '0';
  31. 			LL right = solve(s, i+1, m, n);
  32. 			return left+right;
  33. 		}
  34. 	}
  35. }
  36.  
  37. int main(){
  38. 	int t;
  39. 	cin>>t;
  40. 	while(t--){
  41. 		int n,m;
  42. 		cin>>n>>m;
  43. 		string s;
  44. 		cin>>s;
  45. 		cout<<solve(s,0,m, n)<<"\n";
  46. 	}
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
1
3 5
10_
stdout
copy 
1
https://ideone.com/1T0FZ7
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!