結果

問題 No.315 世界のなんとか3.5
ユーザー parukiparuki
提出日時 2016-06-27 15:14:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,695 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 172,304 KB
実行使用メモリ 45,556 KB
最終ジャッジ日時 2024-10-11 22:23:40
合計ジャッジ時間 6,098 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
28,288 KB
testcase_01 AC 8 ms
23,244 KB
testcase_02 AC 9 ms
22,912 KB
testcase_03 AC 8 ms
23,168 KB
testcase_04 AC 9 ms
22,912 KB
testcase_05 AC 8 ms
22,912 KB
testcase_06 AC 8 ms
23,040 KB
testcase_07 AC 8 ms
23,116 KB
testcase_08 AC 9 ms
23,040 KB
testcase_09 AC 9 ms
23,120 KB
testcase_10 AC 10 ms
23,060 KB
testcase_11 AC 9 ms
23,116 KB
testcase_12 TLE -
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 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

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];
        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;
    }
}
0