QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870203#9680. 数字变换staring#6 2ms7760kbC++142.2kb2025-01-25 15:17:362025-01-25 15:17:44

Judging History

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

  • [2025-01-25 15:17:44]
  • 评测
  • 测评结果:6
  • 用时:2ms
  • 内存:7760kb
  • [2025-01-25 15:17:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace staring
{
    typedef long long LL;
    typedef vector<int> VEC;
    typedef pair<int,int> PII;
    typedef pair<LL,LL> PLL;
    #define fir first
    #define sec second

    #define FOR(i,a,b) for(int i=(a),__i=(b);i<=__i;i++)
    #define ROF(i,a,b) for(int i=(a),__i=(b);i>=__i;i--)

    template<typename TYPE>
    TYPE gmax(TYPE &x,const TYPE y){return x<y?x=y:x;}
    template<typename TYPE>
    TYPE gmin(TYPE &x,const TYPE y){return y<x?x=y:x;}

    static constexpr int SIZE=1<<20;
    static char buffin[SIZE]{},*pin1{},*pin2{};
    static char buffout[SIZE]{},*pout{buffout};
    #define GETC() (pin1==pin2&&(pin2=(pin1=buffin)+fread(buffin,1,SIZE,stdin),pin1==pin2)?EOF:*pin1++)
    #define PUTC(c) (pout-buffout==SIZE&&(fwrite(buffout,1,SIZE,stdout),pout=buffout),*pout++=c)
    template<typename TYPE>
    void read(TYPE &x)
    {
        static int signf{0},chin{0};
        x=signf=0,chin=GETC();
        while(chin<'0'||chin>'9')signf|=chin=='-',chin=GETC();
        while(chin>='0'&&chin<='9')x=(x<<3)+(x<<1)+(chin^48),chin=GETC();
        if(signf)x=-x;
    }
    template<typename TYPE>
    void write(TYPE x,char ch=' ',bool f=0)
    {
        static char stack[64]{},top{0};
        !x&&PUTC('0'),x<0&&(x=-x,PUTC('-'));
        while(x)stack[top++]=x%10|48,x/=10;
        while(top)PUTC(stack[--top]);
        if(ch)PUTC(ch);
    }

}using namespace staring;

constexpr int N=5e6+5,M=45;
constexpr int MOD=998244353;

int f[N][M],vis[N][M];

int solve(int x,int c)
{
    int &v=f[x][c];
    if(vis[x][c])return v;
    if(!c)return v=x==1;

    v=0;
    vis[v][c]=1;
    if(x>1)v=(v+solve(x-1,c-1))%MOD;
    v=(v+solve(x+1,c-1))%MOD;
    if(x>1)v=(v+solve(1,c-1))%MOD;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i)continue;
        v=(v+solve(x/i,c-1))%MOD;
        if(i!=x/i)v=(v+solve(i,c-1))%MOD;
    }
    return v;
}

int main()
{
    int l,r,b;
    read(l),read(r),read(b);

    f[1][0]=vis[1][0]=1;
    FOR(i,l,r)
    {
        int res=0;
        FOR(j,0,b)res=(res+solve(i,j))%MOD;
        write(res);
    }

    fwrite(buffout,1,pout-buffout,stdout);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 1ms
memory: 5712kb

input:

1 10 3

output:

4 10 11 13 14 16 15 18 19 16 

result:

ok 10 numbers

Test #2:

score: 6
Accepted
time: 2ms
memory: 7760kb

input:

1 10 10

output:

1446 3555 5399 8364 9365 13867 13268 18455 18559 22035 

result:

ok 10 numbers

Test #3:

score: 6
Accepted
time: 1ms
memory: 7612kb

input:

1 10 1

output:

1 2 1 1 1 1 1 1 1 1 

result:

ok 10 numbers

Test #4:

score: 6
Accepted
time: 1ms
memory: 5716kb

input:

4 9 10

output:

8364 9365 13867 13268 18455 18559 

result:

ok 6 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #5:

score: 0
Time Limit Exceeded

input:

970000 1000000 40

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

3000000000 3000000000 4

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%