CFR 51 D. Beautiful numbers ( Digit DP )

Problem - D - Codeforces

題意：
問 [ L, R ] 之間有多少整數，是可以被自身的所有非零數位整除。

制約：
T ≤ 10
1 ≤ L, R ≤ 9e18

解法：
考慮 [ 1, x ] 的動態規劃：
一個顯然的狀態可以這樣定義：
dp[ i ][ j ][ k ][ l ]: 考慮前 i 位，模 lcm( 1, 2, .. 9 ) 為何，已出現的數位的集合，是否嚴格小於 x，滿足這些條件的數量。
這個集合如果用二進制表達會有 2^9 這麼多，很浪費。
可以發現其實 lcm( t ), t 屬於 { 1, 2, ... 9 }，只存在 48 種，因此可以做映射進行狀態壓縮。
O3 + avx2 優化壓線通過。

時間 / 空間複雜度：
O( 20 * lcm( 1, 2, .. 9 ) * 50 )

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2") // ターゲットの変更 sse4, avx, avx2 など

#include <bits/stdc++.h>
using namespace std;

int mp[ 2520 + 1 ];
int rmp[ 48 ];

long long dp[ 2 ][ 2520 ][ 48 ][ 2 ];

int lcm( int a, int b ) {
  if( not a or not b ) return a ? a : b;
  return a / __gcd( a, b ) * b;
}

long long solve( long long x ) { // [ 1, x ]
  vector< int > vec;
  for( long long i = x; i; i /= 10 ) {
    vec.emplace_back( i % 10 );
  }
  reverse( vec.begin(), vec.end() );
  memset( dp[ 0 ], 0, sizeof( dp[ 0 ] ) );
  dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1;
  for( int i = 0; i < vec.size(); ++i ) {
    memset( dp[ ~i & 1 ], 0, sizeof( dp[ ~i & 1 ] ) );
    for( int j = 0; j < 2520; ++j ) {
      for( int k = 0; k < 48; ++k ) {
        for( int l = 0; l < 2; ++l ) {
          long long c = dp[ i & 1 ][ j ][ k ][ l ];
          if( not c ) continue;
          int lim = l ? 9 : vec[ i ];
          for( int d = 0; d <= lim; ++d ) {
            dp[ ~i & 1 ][ ( j * 10 + d ) % 2520 ][ mp[ lcm( rmp[ k ], d ) ] ][ l or d < lim ] += c;
          }
        }
      }
    }
  }
  long long res = 0;
  for( int i = 0; i < 2520; ++i ) {
    for( int j = 0; j < 48; ++j ) {
      for( int k = 0; k < 2; ++k ) {
        if( i % rmp[ j ] == 0 ) {
          res += dp[ vec.size() & 1 ][ i ][ j ][ k ];
        }
      }
    }
  }
  return res;
}

signed main() {
  ios::sync_with_stdio( 0 );
  set< int > bag;
  for( int s = 1; s < 1 << 9; ++s ) {
    int l = 1;
    for( int i = 0; i < 9; ++i ) {
      if( s >> i & 1 ) {
        l = lcm( l, i + 1 );
      }
    }
    bag.emplace( l );
  }
  for( auto it = bag.begin(); it != bag.end(); ++it ) {
    static int __ptr = 0;
    mp[ *it ] = __ptr;
    rmp[ __ptr ] = *it;
    ++__ptr;
  }
  int T;
  cin >> T;
  for( int ti = 0; ti < T; ++ti ) {
    long long L, R;
    cin >> L >> R;
    cout << solve( R ) - solve( L - 1 ) << endl;
  }
  return 0;
}