QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #906639 | #9984. The Mysterious Shop | Sorting | AC ✓ | 597ms | 14576kb | C++20 | 1.3kb | 2025-02-20 06:33:32 | 2025-02-20 06:33:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=2e5+5;
int n;
ll dg[N],hd[N],nw[N];
ll g0[N],g1[N],g2[N],g3[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n;
hd[n]=dg[n]=1;
for(int m=n; m>=1 ;m=(m-1)/2){
for(int i=0; i<=m ;i++){
nw[i]=g1[i]=g2[i]=0;
g3[i]=hd[i];
}
int b=m;
for(int i=1; ;i++){
for(int j=0; j*i<=b ;j++){
nw[j]=(nw[j]+g1[j*i]+g2[j*i])%mod;
}
b-=i;
if(b<0) break;
for(int j=b; j>=0 ;j--){
g0[j]=g2[j]=g3[j+i];
if(j+i<=b){
g0[j]=(g0[j]+g0[j+i])%mod;
g2[j]=(g2[j]+2*g2[j+i])%mod;
}
g1[j]=(mod-g0[j]);
}
for(int j=0; j<=b ;j++) g3[j]=g0[j];
/*for(int j=0; j<=3 ;j++) cout << g3[j] << ' ';
cout << endl;*/
}
for(int i=0; i<=m ;i++){
dg[i]=(dg[i]+nw[i])%mod;
hd[i]=nw[i];
}
}
int m=n;
{
for(int i=0; i<=m ;i++){
nw[i]=0;
g3[i]=dg[i];
}
int b=m;
for(int i=1; ;i++){
for(int j=0; j<=b ;j++){
nw[j]=(nw[j]+g3[j])%mod;
}
b-=i;
if(b<0) break;
for(int j=b; j>=0 ;j--){
g0[j]=g3[j+i];
if(j+i<=b){
g0[j]=(g0[j]+g0[j+i])%mod;
}
}
for(int j=0; j<=b ;j++) g3[j]=g0[j];
}
for(int i=0; i<=m ;i++){
cout << nw[m-i] << ' ';
}
cout << '\n';
}
cout << endl;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 13920kb
input:
1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 13924kb
input:
2
output:
1 1 2
result:
ok 3 number(s): "1 1 2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11884kb
input:
3
output:
1 1 1 5
result:
ok 4 number(s): "1 1 1 5"
Test #4:
score: 0
Accepted
time: 0ms
memory: 11880kb
input:
10
output:
1 1 1 2 2 3 5 13 45 180 771
result:
ok 11 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 11872kb
input:
4
output:
1 1 1 3 10
result:
ok 5 number(s): "1 1 1 3 10"
Test #6:
score: 0
Accepted
time: 597ms
memory: 14568kb
input:
200000
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 200001 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 11880kb
input:
2000
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 2001 numbers
Test #8:
score: 0
Accepted
time: 254ms
memory: 13228kb
input:
114514
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 114515 numbers
Test #9:
score: 0
Accepted
time: 595ms
memory: 14568kb
input:
199998
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 199999 numbers
Test #10:
score: 0
Accepted
time: 281ms
memory: 14008kb
input:
123123
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 123124 numbers
Test #11:
score: 0
Accepted
time: 498ms
memory: 14188kb
input:
177777
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 177778 numbers
Test #12:
score: 0
Accepted
time: 594ms
memory: 14576kb
input:
198811
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 198812 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 11892kb
input:
1000
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 1001 numbers
Test #14:
score: 0
Accepted
time: 128ms
memory: 12908kb
input:
73541
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 73542 numbers
Test #15:
score: 0
Accepted
time: 561ms
memory: 14444kb
input:
191919
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 191920 numbers
Test #16:
score: 0
Accepted
time: 208ms
memory: 13264kb
input:
101010
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 101011 numbers
Test #17:
score: 0
Accepted
time: 180ms
memory: 13920kb
input:
91912
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 91913 numbers
Test #18:
score: 0
Accepted
time: 20ms
memory: 12172kb
input:
21213
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 21214 numbers
Test #19:
score: 0
Accepted
time: 165ms
memory: 12820kb
input:
87221
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 87222 numbers
Test #20:
score: 0
Accepted
time: 279ms
memory: 13292kb
input:
123121
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 123122 numbers
Test #21:
score: 0
Accepted
time: 550ms
memory: 14320kb
input:
189111
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 189112 numbers
Test #22:
score: 0
Accepted
time: 563ms
memory: 14440kb
input:
192029
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 192030 numbers
Test #23:
score: 0
Accepted
time: 0ms
memory: 11876kb
input:
7
output:
1 1 1 2 2 6 22 93
result:
ok 8 numbers
Test #24:
score: 0
Accepted
time: 0ms
memory: 13916kb
input:
8
output:
1 1 1 2 2 4 12 45 188
result:
ok 9 numbers
Test #25:
score: 0
Accepted
time: 0ms
memory: 13884kb
input:
9
output:
1 1 1 2 2 3 7 23 88 384
result:
ok 10 numbers
Test #26:
score: 0
Accepted
time: 0ms
memory: 11880kb
input:
114
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8809 9800 10919 12243 14079 17612 27534 62607 197823 733097 2868073 11401259 455266...
result:
ok 115 numbers
Test #27:
score: 0
Accepted
time: 0ms
memory: 11880kb
input:
777
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 778 numbers
Test #28:
score: 0
Accepted
time: 1ms
memory: 11884kb
input:
1342
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 1343 numbers
Test #29:
score: 0
Accepted
time: 2ms
memory: 11844kb
input:
4657
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 4658 numbers
Test #30:
score: 0
Accepted
time: 3ms
memory: 11992kb
input:
7098
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 7099 numbers
Test #31:
score: 0
Accepted
time: 362ms
memory: 14060kb
input:
144324
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 144325 numbers
Test #32:
score: 0
Accepted
time: 135ms
memory: 14052kb
input:
76544
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 76545 numbers
Test #33:
score: 0
Accepted
time: 39ms
memory: 12392kb
input:
34121
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 34122 numbers
Test #34:
score: 0
Accepted
time: 560ms
memory: 14316kb
input:
191981
output:
1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304 2590 2910 3264 3658 4097 4582 5120 5718 6378 7108 7917 8808 9792 10880 12076 13394 14848 16444 18200 20132 22250 24576 27130 29927 32992 3...
result:
ok 191982 numbers
Extra Test:
score: 0
Extra Test Passed