Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define maxN 16
- #define maxLen 505
- using namespace std;
- long long fact[]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000}; /// 0!, 1!, 2!, 3!,..., 15!
- char a[maxN][maxLen]; /// Primul set de siruri (S1)
- char b[maxN][maxLen]; /// Al doilea set de siruri (S2)
- int n,i,j,pi[maxLen];
- int lena[maxN],lenb[maxN]; /// Lungimile sirurilor din primul set (S1) si al doilea set (S2)
- vector<int> v[maxN];
- long long dp[maxN][1<<15]; /// Matricea pentru dinamica
- bool findMatch(int x,int y) /// Cauta potrivirea
- {
- int L=lenb[y];
- int k=0;
- for(int i=1;i<=L;++i)
- {
- while(k>0&&b[y][i]!=a[x][k+1])
- k=pi[k];
- if(b[y][i]==a[x][k+1])
- ++k;
- if(k==lena[x])
- return true;
- }
- return false;
- }
- int main()
- {
- ifstream f("matching.in");
- ofstream g("matching.out");
- f>>n;
- int maxC=(1<<n);
- for(int i=1;i<=n;++i)
- f>>(a[i]+1)>>(b[i]+1),lena[i]=strlen(a[i]+1),lenb[i]=strlen(b[i]+1);
- for(int i=1;i<=n;++i)
- {
- for(int j=1;j<=n;++j)
- if(findMatch(i,j))
- v[i].push_back(j-1);
- }
- dp[0][0] = 1;
- for(int i=1;i<=n;++i) /// Calculez dinamica
- for(int mask=0;mask<maxC;++mask)
- {
- if (i == __builtin_popcount(mask)){
- for(vector<int>::iterator it=v[i].begin();it!=v[i].end();++it)
- if(mask&(1<<(*it)))
- dp[i][mask]+=dp[i-1][mask^(1<<(*it))];
- }
- }
- g<<1LL*(fact[n]-dp[n][maxC-1]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement