fork(1) download
copy 
  1. #line 87 "ColorfulGardenHard.cpp"
  2. #include <iostream>
  3. #include <string>
  4. #include <climits>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <utility>
  11. #include <queue>
  12. #include <stack>
  13. #include <map>
  14. #include<unordered_map>
  15. #include <set>
  16. #include <cstring>
  17. #include <iomanip>
  18. #include <list>
  19. #include <bitset>
  20. //#include<bits/stdc++.h>
  21. #define itn int
  22. #define mp make_pair
  23. #define endl "\n"
  24. using namespace std;
  25. typedef long long ll;
  26. int mod = 1e9 + 7 ;
  27. ll powmod(ll a,ll b) {ll res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
  28. ll gcd(ll a , ll b){return b==0?a:gcd(b,a%b); }
  29. string s1,s2;
  30. ll dp[100010][30],n;
  31.  
  32. ll func(ll mask,ll cur)
  33. {
  34.     ll bits=(ll)__builtin_popcount(mask);
  35.     if(bits==n) return 1;
  36.     if(dp[mask][cur]!=-1)
  37.         return dp[mask][cur];
  38.     ll temp[30];
  39.  
  40.     memset(temp,0,sizeof(temp));
  41.     ll i,j;
  42.     for(j=0;j<n;j++)
  43.     {
  44.         if(mask&(1<<j))
  45.             continue;
  46.         else temp[s1[j]-'a']++;
  47.     }
  48.  
  49.     ll tempans=0;
  50.     for(i=0;i<26;i++)
  51.     {
  52.         if(temp[i]>0 && i!=cur && s2[bits]-'a'!=i)
  53.         {
  54.             //aacout<<"i="<<i<<endl;
  55.             for(j=0;j<n;j++)
  56.             {
  57.                 if(mask&(1<<j))
  58.                 {
  59.                     //cout<<"j in mask="<<j<<endl;
  60.                     continue;
  61.                 }
  62.                 else
  63.                 {
  64.  
  65.                     if(s1[j]-'a'==i)
  66.                     {
  67.                         //cout<<"i="<<i<<endl;
  68.                         tempans=(tempans+func(mask|(1<<j),i))%mod;
  69.                         break;
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     return dp[mask][cur]=tempans;
  76. }
  77.  
  78. class ColorfulGardenHard {
  79. 	public:
  80. 	int count(string garden, string forbid) {
  81.         s1=garden; s2=forbid;
  82.         ll i,j,m,ans=0;
  83.         memset(dp,-1,sizeof(dp));
  84.         ll temp[27];
  85.         memset(temp,0,sizeof(temp));
  86.         for(i=0;i<s1.length();i++)
  87.         {
  88.             temp[s1[i]-'a']++;
  89.         }
  90.         n=s1.length();
  91.         for(i=0;i<26;i++)
  92.         {
  93.             if(temp[i]>0)
  94.             {
  95.                 for(j=0;j<n;j++)
  96.                 {
  97.                     if(s1[j]-'a'==i && s2[0]-'a'!=i)
  98.                     {
  99.                         //cout<<"i="<<i<<endl;
  100.                         ans=(ans+func(1<<j,i))%mod;
  101.                         //cout<<endl<<endl<<endl;
  102.                         break;
  103.                     }
  104.  
  105.                 }
  106.             }
  107.         }
  108.         return ans;
  109.  
  110. 	}
  111. };
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127. // Powered by FileEdit
  128.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/WN1mWT
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!