結果

問題 No.260 世界のなんとか3
ユーザー koyumeishikoyumeishi
提出日時 2015-08-01 00:09:57
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,577 bytes
コンパイル時間 932 ms
コンパイル使用メモリ 87,300 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-18 00:11:40
合計ジャッジ時間 2,318 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
6,812 KB
testcase_01 AC 6 ms
6,940 KB
testcase_02 AC 9 ms
6,940 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
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 -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 4 ms
6,948 KB
testcase_28 AC 17 ms
6,940 KB
testcase_29 AC 25 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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[l][h][j][k] := (h={0,1}, aより確実に小さいか) (j={0,1}, 3が出現したか) (k=0,1,2 , 各桁の和 %3) (l<1000, 下3桁)


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

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


	dp[0][0][0][0] = 1;

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

		if(a.size()-i<=6){
			for(int l=0; l<1000; l++){
				for(int h=0; h<2; h++){
					for(int j=0; j<2; j++){
						for(int k=0; k<3; k++){
							dp_[l][h][j][k] = 0;
						}
					}
				}
			}
		}else{
			int l = 0;
			for(int h=0; h<2; h++){
				for(int j=0; j<2; j++){
					for(int k=0; k<3; k++){
						dp_[l][h][j][k] = 0;
					}
				}
			}
		}

		for(int l=0; l<((a.size()-i <= 6)?1000:1); l++){
			for(int h=0; h<2; h++){
				for(int j=0; j<2; j++){
					for(int k=0; k<3; k++){

						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_l][next_h][next_j][next_k];
							next_pos += dp[l][h][j][k];
							if( next_pos >= MOD ) next_pos -= MOD;

						}
					}
				}
			}
		}

		swap(dp, dp_);
	}

	long long ret = 0;

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

					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