QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#339410#7954. Special NumbersSTnofarjoWA 1ms3768kbC++206.6kb2024-02-27 11:19:382024-02-27 11:19:38

Judging History

你现在查看的是最新测评结果

  • [2024-02-27 11:19:38]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3768kb
查看
  • [2024-02-27 11:19:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pll pair<long long, long long>
#define ppll pair<pll, pll>

const long long mod = 1e9+7;
long long k, pw9[32], pw10[32], ans = 0;
ppll ppk = {{0,0}, {0,0}};
map<ppll, long long> dp[32];
string lo, hi;

long long getDP(long long dig, ppll fac){
    if(dp[dig].count(fac)){
        return dp[dig][fac];
    }else if(dig == 0){
        return (fac.fi.fi == 0 && fac.fi.se == 0 && fac.se.fi == 0 && fac.se.se == 0);
    }
    long long ret = 0;
    ret += getDP(dig-1, fac);
    ret += getDP(dig-1, {{max(fac.fi.fi-1, 0LL), fac.fi.se}, fac.se});
    ret += getDP(dig-1, {{fac.fi.fi, max(fac.fi.se-1, 0LL)}, fac.se});
    ret += getDP(dig-1, {{max(fac.fi.fi-2, 0LL), fac.fi.se}, fac.se});
    ret += getDP(dig-1, {fac.fi, {max(fac.se.fi-1, 0LL), fac.se.se}});
    ret += getDP(dig-1, {{max(fac.fi.fi-1, 0LL), max(fac.fi.se-1, 0LL)}, fac.se});
    ret += getDP(dig-1, {fac.fi, {fac.se.fi, max(fac.se.se-1, 0LL)}});
    ret += getDP(dig-1, {{max(fac.fi.fi-3, 0LL), fac.fi.se}, fac.se});
    ret += getDP(dig-1, {{fac.fi.fi, max(fac.fi.se-2, 0LL)}, fac.se});
    ret %= mod;
    //cout << "dp[" << dig << "][" << fac.fi.fi << "," << fac.fi.se << "," << fac.se.fi << "," << fac.se.se << "]=" << ret << endl;
    dp[dig][fac] = ret; return ret;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    pw9[0] = 1; pw10[0] = 1;
    for(int i=1; i<32; i++){
        pw9[i] = pw9[i-1] * 9 % mod;
        pw10[i] = pw10[i-1] * 10 % mod;
    }
    
    cin >> k >> lo >> hi;
    // cari faktor
    while(k%2 == 0){
        ppk.fi.fi++; k /= 2;
    }
    while(k%3 == 0){
        ppk.fi.se++; k /= 3;
    }
    while(k%5 == 0){
        ppk.se.fi++; k /= 5;
    }
    while(k%7 == 0){
        ppk.se.se++; k /= 7;
    }
    // nambahin 1 ke hi
    bool nabung = true;
    for(int i=hi.length()-1; i>=0 && nabung; i--){
        if(hi[i] == '9'){
            hi[i] = '0';
        }else{
            hi[i]++; nabung = false;
        }
    }
    if(nabung){
        hi = "1" + hi;
    }
    //cout << "lo hi " << lo << " " << hi << endl;

    // ngitung yg ada 0 nya
    // inklusi
    for(int i=0; i<hi.length(); i++){
        ans = (pw10[i] * (hi[hi.length()-1-i] - '0') + ans) % mod;
        //cout << i << ": " << ans << endl;
        if(i){
            //cout << ans << ' ' << pw9[i] << ' ' << (ans + mod - pw9[i]) <<endl;
            ans = (ans + mod - pw9[i]) % mod;
        }
        //cout << i << ": " << ans << endl;
    }
    //ans = (ans + mod - pw9[hi.length()-1] * (hi[0]-'1') % mod) % mod;
    //cout << "ans " << ans << endl;
    //ans = 0;
    for(int i=0; i<lo.length(); i++){
        ans = (ans + mod - pw10[i] * (lo[lo.length()-1-i] - '0') % mod) % mod;
        if(i){
            ans = (ans + pw9[i]) % mod;
        }
    }
    //ans = (ans + pw9[lo.length()-1] * (lo[0]-'1')) % mod;
    //cout << "ans " << ans << endl;
    
    // eksklusi
    for(int i=0; i<hi.length() && hi[i]>'0'; i++){
        //cout << "kurang " << pw9[hi.length()-1-i] * (hi[i]-'1') << endl;
        ans = (ans + mod - pw9[hi.length()-1-i] * (hi[i]-'1') % mod) % mod;
    }    
    for(int i=0; i<lo.length() && lo[i]>'0'; i++){
        //cout << "tambah " << pw9[lo.length()-1-i] * (lo[i]-'1') << endl;
        ans = (ans + pw9[lo.length()-1-i] * (lo[i]-'1')) % mod;
    }

    if(k > 1){
        //cout << k << endl;
        cout << ans << endl; return 0;
    }
    //cout << "sebelum ngitung dp " << ans << endl;
    // ngitung dp deh
    ppll fac = ppk;
    for(int i=1; i<hi.length(); i++){
        ans = (getDP(i, fac) + ans) % mod;
        //cout << "ans jadi " << ans << endl;
    }
    for(int i=0; i<hi.length() && hi[i]>'0'; i++){
        if(hi[i] > '1') ans += getDP(hi.length()-1-i, fac);
        if(hi[i] > '2') ans += getDP(hi.length()-1-i, {{max(fac.fi.fi-1, 0LL), fac.fi.se}, fac.se});
        if(hi[i] > '3') ans += getDP(hi.length()-1-i, {{fac.fi.fi, max(fac.fi.se-1, 0LL)}, fac.se});
        if(hi[i] > '4') ans += getDP(hi.length()-1-i, {{max(fac.fi.fi-2, 0LL), fac.fi.se}, fac.se});
        if(hi[i] > '5') ans += getDP(hi.length()-1-i, {fac.fi, {max(fac.se.fi-1, 0LL), fac.se.se}});
        if(hi[i] > '6') ans += getDP(hi.length()-1-i, {{max(fac.fi.fi-1, 0LL), max(fac.fi.se-1, 0LL)}, fac.se});
        if(hi[i] > '7') ans += getDP(hi.length()-1-i, {fac.fi, {fac.se.fi, max(fac.se.se-1, 0LL)}});
        if(hi[i] > '8') ans += getDP(hi.length()-1-i, {{max(fac.fi.fi-3, 0LL), fac.fi.se}, fac.se});
        ans %= mod; 
        if(hi[i] == '2') fac.fi.fi = max(fac.fi.fi-1, 0LL);
        if(hi[i] == '3') fac.fi.se = max(fac.fi.se-1, 0LL);
        if(hi[i] == '4') fac.fi.fi = max(fac.fi.fi-2, 0LL);
        if(hi[i] == '5') fac.se.fi = max(fac.se.fi-1, 0LL);
        if(hi[i] == '6') fac.fi = {max(fac.fi.fi-1, 0LL), max(fac.fi.se-1, 0LL)};
        if(hi[i] == '7') fac.se.se = max(fac.se.se-1, 0LL);
        if(hi[i] == '8') fac.fi.fi = max(fac.fi.fi-3, 0LL);
        if(hi[i] == '9') fac.fi.se = max(fac.fi.se-2, 0LL);
    }
    //cout << ans << endl;
    fac = ppk;
    for(int i=0; i<lo.length(); i++){
        ans = (ans - getDP(i, fac) + mod) % mod;
    }
    for(int i=0; i<lo.length() && lo[i]>'0'; i++){
        ans -= getDP(i, fac);
        if(lo[i] > '1') ans -= getDP(lo.length()-1-i, fac);
        if(lo[i] > '2') ans -= getDP(lo.length()-1-i, {{max(fac.fi.fi-1, 0LL), fac.fi.se}, fac.se});
        if(lo[i] > '3') ans -= getDP(lo.length()-1-i, {{fac.fi.fi, max(fac.fi.se-1, 0LL)}, fac.se});
        if(lo[i] > '4') ans -= getDP(lo.length()-1-i, {{max(fac.fi.fi-2, 0LL), fac.fi.se}, fac.se});
        if(lo[i] > '5') ans -= getDP(lo.length()-1-i, {fac.fi, {max(fac.se.fi-1, 0LL), fac.se.se}});
        if(lo[i] > '6') ans -= getDP(lo.length()-1-i, {{max(fac.fi.fi-1, 0LL), max(fac.fi.se-1, 0LL)}, fac.se});
        if(lo[i] > '7') ans -= getDP(lo.length()-1-i, {fac.fi, {fac.se.fi, max(fac.se.se-1, 0LL)}});
        if(lo[i] > '8') ans -= getDP(lo.length()-1-i, {{max(fac.fi.fi-3, 0LL), fac.fi.se}, fac.se});
        ans %= mod;
        ans = (ans + mod) % mod; 
        if(lo[i] == '2') fac.fi.fi = max(fac.fi.fi-1, 0LL);
        if(lo[i] == '3') fac.fi.se = max(fac.fi.se-1, 0LL);
        if(lo[i] == '4') fac.fi.fi = max(fac.fi.fi-2, 0LL);
        if(lo[i] == '5') fac.se.fi = max(fac.se.fi-1, 0LL);
        if(lo[i] == '6') fac.fi = {max(fac.fi.fi-1, 0LL), max(fac.fi.se-1, 0LL)};
        if(lo[i] == '7') fac.se.se = max(fac.se.se-1, 0LL);
        if(lo[i] == '8') fac.fi.fi = max(fac.fi.fi-3, 0LL);
        if(lo[i] == '9') fac.fi.se = max(fac.fi.se-2, 0LL);
    }
    cout << ans << endl;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3536kb

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3768kb

input:

1 100 100000

output:

99899

result:

wrong answer 1st lines differ - expected: '99901', found: '99899'
English 繁體中文 简体中文

伺服器時間: 2024-12-03 06:39:03 | 開源專案