結果

問題 No.260 世界のなんとか3
ユーザー koyumeishikoyumeishi
提出日時 2015-07-31 23:49:14
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,205 bytes
コンパイル時間 801 ms
コンパイル使用メモリ 88,392 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-07-18 00:02:28
合計ジャッジ時間 4,626 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
13,756 KB
testcase_01 AC 5 ms
6,940 KB
testcase_02 AC 6 ms
6,940 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#define MOD 1000000007

long long func(string& a){

	// dp[h][j][k][l] := (h={0,1}, aより確実に小さいか) (j={0,1}, 3が出現したか) (k=0,1,2 , 各桁の和 %3) (l<1000, 下3桁)
	vector<vector<vector<vector<long long>>>> dp(2, vector<vector<vector<long long>>>(2, 
		vector<vector<long long>>(3, vector<long long>(1000, 0))));
	dp[0][0][0][0] = 1;

	for(int i=0; i<a.size(); i++){

		vector<vector<vector<vector<long long>>>> dp_(2, vector<vector<vector<long long>>>(2, 
			vector<vector<long long>>(3, vector<long long>(1000, 0))));

		for(int h=0; h<2; h++){
			for(int j=0; j<2; j++){
				for(int k=0; k<3; k++){
					for(int l=0; l<1000; l++){

						for(int v=0; v<10; v++){	//i 桁目の値
							if(h==0 && (a[i] - '0' < v)) continue;

							int next_h = h;
							if(h==0 && (a[i] - '0' > v)) next_h = 1;

							int next_j = j;
							if(j == 0 && v == 3) next_j = 1;

							int next_k = (k+v)%3;
							int next_l = (l * 10 + v) % 1000;

							long long & next_pos = dp_[next_h][next_j][next_k][next_l];
							next_pos += dp[h][j][k][l];
							if( next_pos >= MOD ) next_pos -= MOD;

						}

					}
				}
			}
		}

		swap(dp, dp_);
	}

	long long ret = 0;

	for(int h=0; h<2; h++){
		for(int j=0; j<2; j++){
			for(int k=0; k<3; k++){
				for(int l=0; l<1000; l++){
					long long& val = dp[h][j][k][l];

					if(l%8 == 0) continue;

					if(j==1 && k==0) ret -= val;
					if(j==1) ret += val;
					if(k==0) ret += val;

					ret = (ret+MOD)%MOD;

				}
			}
		}
	}

	return ret;
}

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

	long long ans = func(b);
	ans -= func(a);

	bool a_is = false;
	int tmp = 0;
	for(int i=0; i<a.size(); i++){
		if(a[i] == '3'){
			a_is = true;
		}
		tmp = (tmp+a[i]-'0') % 3;
	}
	if(tmp%3 == 0) a_is = true;

	reverse(a.begin(), a.end());
	tmp = 0;
	int k = 1;
	for(int i=0; i<3 && i<a.size(); i++){
		tmp += (a[i] - '0') * k;
		k *= 10;
	}
	if(tmp % 8 == 0) a_is = false;
	if(a_is) ans++;
	ans = (ans+MOD) % MOD;
	cout << ans << endl;

	return 0;
}
0