QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#51564#4543. SumireAmalgadon#WA 596ms3656kbC++173.4kb2022-10-02 17:03:042022-10-02 17:03:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-02 17:03:05]
  • 评测
  • 测评结果:WA
  • 用时:596ms
  • 内存:3656kb
  • [2022-10-02 17:03:04]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cstring>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)

#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to

using namespace std;

typedef long long LL;

const int N = 66;
const int mod = 1e9 + 7;

int B, d;

LL qpow(LL a, LL b)
{
    LL ret = 1, base = a;
    while (b) {
        if (b & 1) ret = ret * base % mod;
        base = base * base % mod, b >>= 1;
    }
    return ret;
}

void up(LL &a, LL b) { a = (a + b) % mod;}

LL f[N][N][2], num[N];

LL dfs(int i, int j, int k)
{
    if (i == -1) return !j;
    if (f[i][j][k] != -1) return f[i][j][k];
    LL sum = 0;
    if (k) {
        if (d > num[i]){
            up(sum, dfs(i - 1, j, 1));
            up(sum, dfs(i - 1, j, 0) * num[i]);
        }
        else if (d == num[i]) {
            up(sum, dfs(i - 1, j - 1, 1));
            up(sum, dfs(i - 1, j, 0) * num[i]);
        }
        else {
            up(sum, dfs(i - 1, j, 1));
            up(sum, dfs(i - 1, j - 1, 0));
            up(sum, dfs(i - 1, j, 0) * (num[i] - 1));
        }
    }
    else {
        up(sum, dfs(i - 1, j - 1, 0));
        up(sum, dfs(i - 1, j, 0) * (B - 1));
    }
    f[i][j][k] = sum;
    //cout << i << " " << j << " " << k << " " << f[i][j][k] << endl;
    return f[i][j][k];
}

LL ans[N];

LL calc(LL lim, int k)
{
    memset(f, -1, sizeof(f));
    Rep0(i, 60) num[i] = lim % B, lim /= B;
    //Rep0(i, 60) cout << num[i] << " ";
    //cout << endl;

    bool flag = false;
    Rep(i, 60) ans[i] = 0;
    for (int i = 60; i >= 0; i --) {
        if (!flag) {
            if (num[i] >= 1) {
                
                flag = true;
                if (d > num[i]){
                    Rep(j, 60) up(ans[j], dfs(i - 1, j, 1));
                    Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 1));
                }
                else if (d == num[i]) {
                    Rep(j, 60) up(ans[j], dfs(i - 1, j - 1, 1));
                    Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 1));
                }
                else{

                    if (d > 0){
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 1));
                        Rep(j, 60) up(ans[j], dfs(i - 1, j - 1, 0));
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 2));
                    }
                    else {
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 1));
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 1));
                    }
                }
            }
        }
        else {
            if (d > 0){
                Rep(j, 60) up(ans[j], dfs(i - 1, j - 1, 0));
                Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (B - 2));
            }
            else Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (B - 1));
        }
    } 
    LL ret = 0;
    Rep(i, 60){
        up(ret, qpow(i, k) * ans[i]);
        //if (ans[i]) cout << i << " " << ans[i] << " " << qpow(ans[i], k) << endl;
    }
    //cout << ret << endl;
    return ret;
}

int main()
{
    int T;
    cin >> T;
    while (T --){

        int k;
        LL l, r;

        cin >> k >> B >> d >> l >> r;

        cout << (calc(r, k) - calc(l - 1, k) + mod) % mod << endl;
        
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 596ms
memory: 3656kb

input:

10000
3 207891369 69789899 964252340141144201 993463302889356041
3 747663427 196567324 607861784354966835 737019014793415965
7 4 1 75021281026163040 281275352760223247
159801714 6 4 57793681483331990 719907284728404544
760336565 3 2 640278753805042190 790056554571568287
3 3 0 370833904610234656 7289...

output:

348402080
920411258
43957847
394377489
325566292
16698845
200062394
375991223
465046227
263340736
704957449
700015274
345964631
546866401
355527840
509741157
165223493
924963116
97531004
174290409
257548623
852781447
29936714
204554940
926403980
440327688
351876140
824109444
874138235
745424255
3977...

result:

wrong answer 3rd lines differ - expected: '659717287', found: '43957847'