結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー koyumeishi
提出日時 2015-08-01 00:24:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 2,469 bytes
コンパイル時間 940 ms
コンパイル使用メモリ 87,424 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-07 18:05:56
合計ジャッジ時間 2,373 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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++){

		for(int l=0; l<( (a.size()-i < 10)?1000:1 ); 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;
					}
				}
			}
		}
		

		for(int l=0; l<( (a.size()-i < 10)?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 = 0;
							if(a.size()-i < 5) 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+MOD)%MOD;
}

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