QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#870203 | #9680. 数字变换 | staring# | 6 | 2ms | 7760kb | C++14 | 2.2kb | 2025-01-25 15:17:36 | 2025-01-25 15:17:44 |
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%