結果

問題 No.220 世界のなんとか2
ユーザー srup٩(๑`н´๑)۶srup٩(๑`н´๑)۶
提出日時 2016-08-12 03:51:23
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,885 bytes
コンパイル時間 560 ms
コンパイル使用メモリ 64,440 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-25 02:23:59
合計ジャッジ時間 1,046 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0