Concise and clear CodeForces - 991F(dfs 有重复元素的全排列)

就是有重复元素的全排列

#include <bits/stdc++.h>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long LL;

const int maxn = , INF = 0x7fffffff;

char str[maxn];

int vis[maxn], v[maxn];

LL num[maxn];

LL res = ;

void init()

{

    num[] = ;

    for(int i=; i<maxn; i++)

        num[i] = num[i-] * i;

}

void dfs(LL x, LL cnt)

{

    if(cnt == )

    {

        if(x > ) return;

        LL ans1 = , ans2 = , ans3 = ;

        for(int i=; i<=; i++)

        {

            ans2 += v[i];

        }

        LL temp = ans2;

        ans2 = num[ans2];

        for(int i=; i<=; i++)

            ans2 /= num[v[i]];

    //    cout<< ans2 <<endl;

        if(v[])

        {

            ans3 = num[temp-];

            for(int i=; i<=; i++)

                if(i == ) ans3 /= num[v[i]-];

                else ans3 /= num[v[i]];

            ans2 -= ans3;

        }

        res += ans2;

        return;

    }

    if(!vis[cnt])

        dfs(x, cnt+);

    else

        for(int i=; i<vis[cnt] && i<=x; i++)

        {

            v[cnt] += i;

            dfs(x-i, cnt+);

            v[cnt] -= i;

        }

}

int main()

{

    init();

    cin>> str;

    int len = strlen(str);

    int maxx = -INF;

    LL sum = , ans = , flag = ;

    for(int i=; i<len; i++)

    {

        if(i != )

            if(str[i] != str[i-])

                flag = ;

        vis[str[i]-'']++;

        if(vis[str[i]-''] == ) ans++;

    }

    if(!flag)

    {

        cout<< len <<endl;

        return ;

    }

    res += num[ans];

    if(vis[])

        res -= num[ans-];

    for(int i=; i<=; i++)

        if(vis[i])

            sum += vis[i]-;

    for(int i=; i<=sum; i++)

    {

        for(int i=; i<=; i++)

            if(vis[i])

                v[i] = ;

            else

                v[i] = ;

        dfs(i, );

    }

    cout<< res <<endl;

    return ;

}