AtCoder Beginner Contest 178, C : Ubiquity

問題文

　https://atcoder.jp/contests/abc178/tasks/abc178_c

問題概要

　長さ $N$ の正整数列 $\{ A_i \}$ で，次の条件をすべて満たすものの個数を $\pmod 10^9 + 7$ で求めよ．

• $0 \leq A_i \leq 9$
• $\exists i, A_i = 0$
• $\exists i, A_i = 9$

制約

• $1 \leq N \leq 10^6$

解法

　Digit DP 的な DP で計算できます．具体的には，

• dp[ 決めた桁数 ][ $0$, $9$ の使用状況を 2 bit にエンコードしたもの ] := ways

とします．各状態からの遷移では，次に入れる数字を $0$ から $9$ の全通り試し，2 bit のフラグを適切に更新します．
　計算量としては定数倍が消えるので，$\Theta( N )$ です．

コード

constexpr int MOD = 1'000'000'007;

int main()
{
	IN( int, N );

	static int dp[ 1 << 20 ][ 1 << 2 ];
	dp[0][0] = 1;
	// dp[ # of decided digits ][ flags (2 bits) ] := ways

	REP( i, N )
	{
		REP( j, 1 << 2 )
		{
			REP( d, 10 )
			{
				const int nj = j | ( d == 0 ? 1 : 0 ) | ( d == 9 ? 2 : 0 );
				( dp[ i + 1 ][ nj ] += dp[i][j] ) %= MOD;
			}
		}
	}

	cout << dp[N][3] << endl;

	return 0;
}