結果

問題 No.220 世界のなんとか2
コンテスト
ユーザー wunderkammer2
提出日時 2020-02-14 13:06:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,552 bytes
コンパイル時間 1,073 ms
コンパイル使用メモリ 101,500 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-06 07:53:16
合計ジャッジ時間 1,918 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)

#define vll    vector<ll>
#define vvll   vector<vector<ll>>
#define all(x) (x).begin(),(x).end()


int main()
{	
	int P;
	cin >> P;

	string N = "1";
	rep(i, P) N += "0";

	// dp[i][j][k] := 条件を満たす数の個数
	//i:=決めた桁数
	//j:=未満フラグ
	//k:=0～2・・・1～i桁目までの数字の合計を3で割ったあまり。
	//   3・・・・1～i桁目までに3が一度でも使われた
	vector<vvll> dp(N.size() + 1, vvll(2, vll(4, 0)));
	dp[0][0][0] = 1;

	rep(i, N.size())
	{
		//先頭桁のみ
		int D = N[i] - '0';

		rep(j, 2)
		{
			reple(k, 0, 3)
			{
				reple(d, 0, (j ? 9 : D))
				{
					//3が一度でも使われた場合は条件を必ず満たすため、和の考慮不要
					if (k == 3 || d == 3)
					{
						dp[i + 1][j || (d < D)][3] += dp[i][j][k];
					}
					else
					{
						int sum = (k + d) % 3;
						dp[i + 1][j || (d < D)][sum] += dp[i][j][k];
					}
				}
			}
		}
	}

	//結果に「0」が含まれるため、-1する。
	cout << dp[N.size()][0][0] + dp[N.size()][0][3] + dp[N.size()][1][0] + dp[N.size()][1][3] - 1<< endl;

	return 0;
}
0