No.220 世界のなんとか2 - yukicoder
- 桁 DP で解く問題。3 の倍数をどうやって桁 DP に組み込むのかというと、ある桁までの mod 3 の値を状態として持っておけばよい。
- 計算解として 10^p - 1 - 2/3 * 9^p ってのもあるらしい。
- とりあえず強引にでも DP で解けるようになりたい。
class SomethingOfWorld2
{
public:
void solve(void)
{
int p;
cin>>p;
--p;
vector<vector<vector<ll>>> dp(p+1,vector<vector<ll>>(2,vector<ll>(3,0)));
REP(k,10)
{
if ( k == 3 )
++dp[0][1][k%3];
else
++dp[0][0][k%3];
}
ll ten = 10;
REP(i,p)
{
REP(j,3)
REP(k,10)
{
int l = (ten*k + j)%3;
if ( k == 3 )
dp[i+1][1][l] += dp[i][0][j];
else
dp[i+1][0][l] += dp[i][0][j];
dp[i+1][1][l] += dp[i][1][j];
}
ten *= 10;
}
ll cnt = 0;
REP(i,3)
cnt += dp[p][1][i];
cnt += dp[p][0][0];
cout<<(cnt-1)<<endl;
}
};