codeforce 991E(조합수 반복 검색)

2175 단어 사유조합수
제목 링크: 링크 열기 클릭
샤오밍이 헷갈릴 때 본 자동차 번호판 숫자를 실제 숫자와 비교해 보자.
① 실제로 나온 숫자는 샤오밍이 다 봤다
② 샤오밍은 같은 숫자만 보고 적을 수는 없다
③ 차량 번호는 전도 제로가 없다
실제 숫자가 몇 가지가 될 수 있는지 물어보세요.
먼저 모든 숫자가 나타나는 횟수를 기록해라. 이것이 바로 검색할 때 모든 숫자가 얻는 상한선이다
0부터 9까지 반복(10층 순환에 해당하며, 여기서 귀속적인 방식으로 실현되며, 각 층의 순환 횟수는 바로 이 층의 숫자가 나타나는 횟수이며, 이 수를 얼마나 취하는지를 나타낸다)
마지막 단계에서 현재 이 숫자로 합법적인 숫자의 개수 ans=총 숫자 총체의 곱셈/(∏각 숫자의 출현 횟수의 곱셈)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define sqr(a) (a)*(a)
#define For(i,m,n) for(int i=m;i<=n;i++)
#define Dor(i,n,m) for(int i=n;i>=m;i--)
#define lan(a,b) memset(a,b,sizeof(a))
#define maxn 100010

using namespace std;

LL num[10];
LL fact[20];
LL nownum[10];
LL ans;

void init()
{
    lan(num,0);
    lan(fact,0);
    lan(nownum,0);
    fact[0]=1;
    for(int i=1;i<=19;i++)
        fact[i]=i*fact[i-1];
}

LL cal()
{
    LL tem=0;
    for(int i=0;i<=9;i++)
        tem+=nownum[i];
        //printf("%lld
",tem);
    tem=fact[tem];
        //printf("%lld
",tem);
    for(int i=0;i<=9;i++)
    {
        tem/=fact[nownum[i]];
    }
        //printf("%lld
",tem);
    return tem;
}

void pou(int x)
{
   // printf("x=%d
",x);
    if(x>9)
    {
        ans+=cal();
        //printf("ans=%lld
",ans);
        if(nownum[0]>=1)
        {
            nownum[0]--;
            ans-=cal();
            nownum[0]++;
       // printf("ans=%lld
",ans);
        }
        return;
    }
    if(num[x])
    {
        for(int i=1;i<=num[x];i++)
            nownum[x]=i,pou(x+1);
    }
    else
        pou(x+1);
}

int main()
{
    LL n;
    while(~scanf("%lld",&n))
    {
        init();
        ans=0;
        while(n)
        {
            num[n%10]++;
            n/=10;
        }
        pou(0);
        printf("%lld
",ans);
    }
    return 0;
}
leetcode10+leetcode44 정규 일치 문제 요약
SwiftUI의 종속 주입

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage