torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #235, D : Roman and Numbers

問題概要

 18 桁以下の整数 n と、100 以下の整数 m が与えられる。次の condition をすべて満たすような整数の数を求めよ。

  • n の各桁の並び替えによって得られる
  • Leading Zero をもたない
  • modulo m の値が 0

解法

 よくある数え上げっぽいので、DP できないか考えます。単純にやろうとすると、各数字を何回使ったかをパラメータにしなければなりませんが、この問題では、桁数が高々 18 であることを利用できます。すなわち、各数字にユニークな番号を振って、使用済みの番号を集合としてエンコードすると、これは 18 bit に収まります。さほど大きくない値なので、この値を DP のキーにすることができて、次のような DP を考えることができます。

  • dp[ 既に使った数字の集合が s ][ mod m の値が i ][ k := Leading Zero が終わっていたら 1 、それ以外で 0 ] := 総数

dp[ s ][ i ][ j ] からの更新では、次に使う数字を全て試して、遷移先の状態を更新します。k 番の数字を使うことにしたとき、遷移先の状態のそれぞれのパラメータ ns, ni, nj は、k 番の数字が表す値を d とすると、

  • ns := s | 1 << k
  • ni := ( i * 10 + d ) % m
  • nj = j || d != 0

として計算されます。更新時、数字に振られた番号が違っていても数字が異なるとは限らないので、同じ数字を使う遷移を複数回数え上げないようにする必要があります。
 以上の計算が終わったあと、dp[ ( 1 << n ) - 1 ][ 0 ][ 1 ] に答えが求まっています。

コード

typedef long long LL;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

LL dp[ 1 << 18 ][ 100 ][ 2 ];

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string nums;
	cin >> nums;
	sort( ALL( nums ) );

	const int n = nums.size();
	const int p1 = upper_bound( ALL( nums ), '0' ) - nums.begin();

	int m;
	cin >> m;

	dp[0][0][0] = 1;

	REP( s, 0, 1 << n )
	{
		REP( i, 0, m )
		{
			REP( j, 0, 2 )
			{
				if ( dp[s][i][j] == 0 )
				{
					continue;
				}

				vector<bool> done( 10 );
				REP( k, j ? 0 : p1, n )
				{
					const int d = nums[k] - '0';
					if ( s & 1 << k || !j && d == 0 || done[d] )
					{
						continue;
					}

					const int ns = s | 1 << k;
					const int ni = ( i * 10 + d ) % m;
					const int nj = j || d != 0;

					dp[ ns ][ ni ][ nj ] += dp[s][i][j];

					done[d] = true;
				}
			}
		}
	}

	cout << dp[ ( 1 << n ) - 1 ][0][1] << endl;

	return 0;
}