#110091 (C++11) No.220 世界のなんとか2

• 問題: No.220 世界のなんとか2
• ユーザー: srup٩(๑`н´๑)۶
• 提出日時: 2016-08-12 03:51:23
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,885 bytes
• コンパイル時間: 660 ms
• コンパイル使用メモリ: 64,052 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-07 11:56:06
• 合計ジャッジ時間: 1,332 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)


//dp[i][j][k][l]
//整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。
//k=1の時はすでにi番目までに数字3を含んでいて、k=0の時は含まれていない。 lはi番目の桁まで考えた時のmod3の値
long long dp[30][2][2][3];
static const int mod = 1e9 + 7;

int main(void){
	int p; cin >> p;
	string a;
	a += '1';
	rep(i, p) a += '0';

	dp[0][0][0][0] =  1;//初期
	rep(i, p + 1){
		rep(j, 2){
			int lim = j ? 9 : a[i] - '0';
			/*
			if(j == 1) lim = 9;//i桁目までですでに未満が決まっていればi+1桁目の数字は何でもよい
			else if(j == 0 && i == 0) lim = 1;//未満が決まっていなくても１ケタ目には１を入れる場合がある
			else lim = 0;//未満が決まっていなければ0しか入れられない
			*/

			rep(k, 2){
				rep(l, 3){
					rep(m, lim + 1){
						// printf("i:%d j:%d k:%d l:%d m:%d", i, j, k, l, m);

						(dp[i + 1][j || m < lim][k || m == 3][(l + m) % 3] += dp[i][j][k][l]) %= mod;
						// printf("  dp) = %lld\n", dp[i + 1][j || m < lim][k || m == 3][(l + m) % 3]);
						/*
						printf("m = %d  lim = %d\n", m, lim);
						printf("dp[%d][%d][%d][%d] = %lld  ", i + 1, j || m < lim, k || m == 3, (l+m)%3, dp[i + 1][j || m < lim][k || m == 3][(l + m) % 3]);
						printf("dp[%d][%d][%d][%d] = %lld", i, j, k, l, dp[i][j][k][l]);
						printf("\n");
						*/
					}
				}
			}
		}
	}

	long long ans = 0;
	rep(j, 2) rep(k, 2) rep(l, 3){
		if(k == 1|| l == 0){
			(ans += dp[p + 1][j][k][l]) %= mod;
		}
	}
	cout << ans - 1 << endl;
	return 0;
}