結果

問題 No.315 世界のなんとか3.5
ユーザー paruki
提出日時 2016-06-27 15:17:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 2,728 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 171,460 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-10-11 22:23:58
合計ジャッジ時間 5,930 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const int MOD=(int)1e9+7;
void add(int &x, int y){
x+=y;
if(x>=MOD)x-=MOD;
}
const int MAX = (int)2e5 + 1;
int dp1[MAX][2][2][2][3], dp2[10][2][2][2][3][25][32];
char SA_[MAX], SB_[MAX];
string A, B;
int P, LEN, pow5, pow2;
int f(int pos, int greaterThanA, int lessThanB, int use3, int m3, int m25, int m32){
if(LEN - pos < 6){
int cur = pos - LEN + 5;
int &res = dp2[cur][greaterThanA][lessThanB][use3][m3][m25][m32];
if(res != -1)return res;
if(pos == LEN){
if(m3 != 0 && use3 == 0)return res=0;
else if(m25%pow5==0 && m32%pow2==0) return res=0;
else return res = 1;
}
res = 0;
rep(digit, 10){
if(greaterThanA == 0 && digit < A[pos])continue;
if(lessThanB == 0 && digit > B[pos])continue;
int n3 = (m3 * 10 + digit) % 3;
int n25 = (m25 * 10 + digit) % 25;
int n32 = (m32 * 10 + digit) % 32;
add(res,
f(pos + 1, greaterThanA | (digit>A[pos]), lessThanB | (digit < B[pos]), use3 | (digit == 3), n3, n25, n32));
}
return res;
} else{
int & res = dp1[pos][greaterThanA][lessThanB][use3][m3];
if(res != -1)return res;
res = 0;
rep(digit, 10){
if(greaterThanA == 0 && digit < A[pos])continue;
if(lessThanB == 0 && digit > B[pos])continue;
int n3 = (m3 * 10 + digit) % 3;
add(res,
f(pos + 1, greaterThanA | (digit>A[pos]), lessThanB | (digit < B[pos]), use3 | (digit == 3), n3, 0, 0));
}
return res;
}
}
int main(){
while(~scanf("%s%s%d", SA_, SB_, &P)){
A = string(SA_);
B = string(SB_);
int dif = sz(B) - sz(A);
if(dif)A = string(dif, '0') + A;
each(c, A)c -= '0';
each(c, B)c -= '0';
LEN = sz(A);
MEM(dp1, -1);
MEM(dp2, -1);
for(int i = 25; i; i /= 5)if(P%i == 0){
pow5 = i;
break;
}
for(int i = 32; i; i /= 2)if(P%i == 0){
pow2 = i;
break;
}
int ans = f(0, 0, 0, 0, 0, 0, 0);
cout << ans << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0