結果

問題 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;
    }
}
0