fork(3) download
copy 
  1. //Ishan Bansal
  2. //handle:ishan.nitj at codeforces ,ishan_nitj at codechef
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define lll __int128
  7. #define mag 1000000
  8. #define inf 1000000000000000000
  9. #define MOD 1000000007
  10. #define rep(i,n) for(i=0;i<n;i++)
  11. #define mset(x,v) memset(x, v, sizeof(x))
  12. #define print_array(a,n) for(i=0;i<n;i++) printf("%lld ",a[i]);
  13. #define dbg1(x) cout<<#x<<" "<<x<<endl;
  14. #define dbg2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
  15. #define dbg3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
  16. #define dbg4(x,y,z,k) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<" "<<#k<<" "<<k<<endl;
  17. #define pb push_back
  18. #define fe first
  19. #define se second
  20.  
  21. ll dp[15][1<<15];
  22. string g,f;
  23. ll n;
  24.  
  25. ll count_one(ll n){// to count no of ones in a binary form of a number
  26. 	ll count=0;
  27. 	while(n){
  28. 		n=n&(n-1);
  29. 		count++;
  30. 	}
  31. 	return count;
  32. }
  33.  
  34. ll func(ll last,ll mask){
  35. 	if(dp[last][mask]!=-1)
  36. 	return dp[last][mask];
  37. 	ll pos=count_one(mask)-1;
  38. 	ll ans=0;
  39. 	if(count_one(mask)==1){
  40. 	if(mask&(1<<last))
  41. 	ans=1;
  42. 	}
  43. 	else{
  44. 		set<char>s;
  45. 		mask=mask&~(1<<last);
  46. 		for(ll k=0;k<n;k++){
  47. 			if(mask&(1<<k)){
  48. 				if(g[k]!=g[last] && s.find(g[k])==s.end() && f[count_one(mask)-1]!=g[k]){
  49. 					s.insert(g[k]);
  50. 					ans+=func(k,mask);
  51. 				}
  52. 			}
  53.  
  54. 		}
  55. 	}
  56. dp[last][mask]=ans;
  57. return ans;
  58. }
  59.  
  60. int main(){
  61. 	mset(dp,-1);
  62. 	cin>>g>>f;
  63. 	n=g.size();
  64. 	ll ans=0;
  65. 	set<char>s;
  66. 	for(ll i=0;i<n;i++){
  67. 	if(s.find(g[i])==s.end()){
  68. 	ans+=func(i,(1<<n)-1);
  69. 	s.insert(g[i]);	
  70. 	}
  71. 	}
  72. 	cout<<(ans);
  73. }
  74.  
Success #stdin #stdout 0.01s 7308KB
comments (?)
stdin
copy 
aabbcc
aabbcc
stdout
copy 
5
https://ideone.com/443DkL
language:
C++14 (gcc 8.3)
created:
8 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!