codeforces 401D D. Roman and Numbers(상태 압축 dp+ 수론)

제목 링크:


codeforces 401D

제목 대의:


숫자num과 숫자mod를 제시하고num의 숫자를 다시 배열하며,mod를 정제할 수 있는 방안의 수를 물어보십시오.

제목 분석:


4
  • 먼저 우리는 S를 하나의 숫자의 집합으로 정의했다. dp[s][num]는 S의 숫자를 이용하여%mod를 구성하는 여수가num인 방안수를 나타낸다

  • 4
  • 그럼 초기 상태는 dp[0][0]=1
  • 4
  • 이동은 모든 숫자를 매거하여 새로운 상태 s|(1<4
  • 어떤 숫자는 같은 숫자가 나오기 때문에 마지막에 모든 숫자 내부에 전체 배열이 있는 상황을 제외해야 한다.

  • AC 코드:

    #include 
    #include 
    #include 
    #include 
    #define MAX (1<<18)
    
    using namespace std;
    
    typedef long long LL;
    
    LL dp[MAX][107];
    int n,m;
    LL fac[MAX];
    int num[MAX];
    char s[50];
    
    int main ( )
    {
        while ( ~scanf ( "%s" , s ) )
        {
            scanf ( "%d" , &m );
            n = strlen ( s );
            int total = 1<memset ( num , 0 , sizeof ( num ) );
            memset ( dp , 0 , sizeof ( dp ) );
            dp[0][0] = 1;
            fac[0] = 1;
            for ( LL i = 0 ; i < n ; i++ )
            {
                fac[i+1] = fac[i]*(i+1LL);
                num[s[i]-48]++;
            }
            for ( int i = 0 ; i < total ; i++ )
                for ( int k = 0 ; k < m ; k++ )
                {
                    if ( !dp[i][k] ) continue;
                    for ( int j = 0 ; j < n ; j++ )
                    {
                        int x = s[j]-48;
                        if ( x == 0 && i == 0 ) continue;
                        if ( (1<continue;
                        int y = (1<int z = (k*10LL+x)%m;
                        dp[y][z] += dp[i][k];
                    }
                }
            LL temp = 1;
            for ( int i = 0 ; i < 10 ; i++ )
                temp *= fac[num[i]];
            printf ( "%lld
    "
    , dp[total-1][0]/temp ); } }

    좋은 웹페이지 즐겨찾기