CFR 401 D. Roman and Numbers ( DP, Digit, Bitmask )

Problem - D - Codeforces

題意：
給你一個數 N，和 M。求 N 有幾種排列 N'，使得 N' 整除 M 且沒有領導零。

資料規模：
n (1 ≤ n < 1e18) and m (1 ≤ m ≤ 100)
TL: 4000 ms
ML: 512 MB

解法：
感覺就不太妙。考慮 dp，先有 M 這一維，然後 18 這數字感覺就很數位統計的 fu，在這裡又發現，如果從左邊的數字決定到右邊，只要當前的數除以 M 的餘數相同，使用的順序根本不重要。因此考慮用 bitmask。
dp[ s ][ i ]：集合 s 的數字已使用，目前的數字除以 m 的餘數為 i 的情況數。
( ex. 如果 s 集合為 { 0, 3 }，代表 N 的第 0 位數以及第 3 位數已使用 )
狀態轉移很顯然，可以參考代碼。

時間 / 空間複雜度：
O( 2^N * M * N ) / O( 2^N * M )

ll N, M;

void init(){
  cin >> N >> M;
}

vi A;
vvl dp;

void preprocess(){
  for( ll v = N; v; v /= 10 ){
    A.emplace_back( v % 10 );
  }
  reverse( A.begin(), A.end() );
  dp = vvl( 1 << ( int ) A.size(), vl( M ) );
  dp[ 0 ][ 0 ] = 1;
  for( int s = 0; s < 1 << ( int ) A.size(); ++s ){
    for( int m = 0; m < M; ++m ){
      for( int i = 0; i < A.size(); ++i ){
        if( s & 1 << i ) continue;
        if( s == 0 and A[ i ] == 0 ) continue; // no leading zero allowed
        dp[ s | 1 << i ][ ( m * 10 + A[ i ] ) % M ] += dp[ s ][ m ];
      }
    }
  }
}

void solve(){
  vi cnt( 10 );
  for( int i = 0; i < A.size(); ++i ){
    ++cnt[ A[ i ] ];
  }
  ll ans = dp[ ( 1 << ( int ) A.size() ) - 1 ][ 0 ];
  for( int i = 0; i < 10; ++i ){
    for( int j = 1; j <= cnt[ i ]; ++j ){
      ans /= j;
    }
  }
  cout << ans << endl;
}