結果

問題 No.260 世界のなんとか3
ユーザー めうめう🎒めうめう🎒
提出日時 2016-11-20 15:44:46
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,657 bytes
コンパイル時間 523 ms
コンパイル使用メモリ 74,188 KB
実行使用メモリ 8,464 KB
最終ジャッジ日時 2023-08-18 04:22:22
合計ジャッジ時間 3,379 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,324 KB
testcase_01 AC 5 ms
7,232 KB
testcase_02 AC 5 ms
7,060 KB
testcase_03 WA -
testcase_04 AC 106 ms
8,244 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 31 ms
7,676 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 48 ms
7,888 KB
testcase_13 WA -
testcase_14 AC 70 ms
8,028 KB
testcase_15 AC 22 ms
7,264 KB
testcase_16 AC 62 ms
7,888 KB
testcase_17 WA -
testcase_18 AC 48 ms
7,680 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 56 ms
7,960 KB
testcase_25 AC 56 ms
8,464 KB
testcase_26 AC 56 ms
8,176 KB
testcase_27 AC 5 ms
7,092 KB
testcase_28 AC 105 ms
8,204 KB
testcase_29 AC 106 ms
8,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair
#define MOD 1000000007

string a, b;

int memo[10001][2][2][3][8];

int saiki(int now, bool isSame, bool has3, int mod3, int mod8){

	if(now == a.size() && (has3 || mod3 == 0) && mod8 != 0) return 1;
	if(now == a.size()) return 0;

	if(memo[now][isSame][has3][mod3][mod8] != INF) return memo[now][isSame][has3][mod3][mod8];

	int ret = 0;

	for(int i = 0;i < 10;i++){
		if(isSame && a[now] < ('0' + i)) continue;

		bool nextIsSame;
		if(isSame && a[now] == ('0' + i)) nextIsSame = true;
		else nextIsSame = false;

		bool nextHas3 = (has3 || i == 3);

		int nextMod3 = (mod3 + i) % 3;

		int nextMod8 = (mod8 * 10 + i) % 8;

		ret += saiki(now + 1, nextIsSame, nextHas3, nextMod3, nextMod8) % MOD;
		ret %= MOD;
	}

	return memo[now][isSame][has3][mod3][mod8] = ret % MOD;
}

void init(){
	REP(i, 10001) REP(j, 2) REP(k, 2) REP(l, 3) REP(m, 8){
		memo[i][j][k][l][m] = INF;
	}
}

int main() {
	cin >> b >> a;

	for(int i = b.size() - 1;i >= 0;i--){
		if(b[i] == '0'){
			b[i] = '9';
		}else {
			b[i] = (b[i] - 1);
			break;
		}
	}
	if(b[0] == '0' && b.size() != 1) b.erase(0, 1);

	init();
	int ans = saiki(0, 1, 0, 0, 0) % MOD;

	a = b;
	init();
	int ans2 = saiki(0, 1, 0, 0, 0) % MOD;

	// cout << ans << endl << ans2 << endl;

	cout << ans - ans2 << endl;
	return 0;
}
0