QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#905646 | #1465. Not Our Problem | yinhee | AC ✓ | 40ms | 23268kb | C++14 | 2.9kb | 2025-02-19 14:34:38 | 2025-02-19 14:34:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>
il void read(T &x){
int f=1;x=0;char c=gc();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=gc();
}
while(c>='0'&&c<='9'){
x=x*10+c-48,c=gc();
}
x*=f;
}
template<typename T,typename ...Args>
void read(T &x,Args &...args){
read(x),read(args...);
}
template<typename T>
il void write(T x){
char buf[43];int len=0;
if(x<0){
pc('-'),x=-x;
}
do{
buf[++len]=x%10,x/=10;
}while(x);
while(len){
pc(buf[len--]+'0');
}
}
}
using namespace my_std;
const int N=1e6+7,M=-1,inf=0x3f3f3f3f,mod=998244353;
const ll INF=1ll*inf*inf;
int n,s[N];
ll m,lim,a[N],L[N];
il int Mod(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
ll myCbrt(ll x){
rep(i,0,1e6+1){
if(1ll*i*i*i>x){
return i-1;
}
}
assert(0);
}
il ll calc(ll x){
if(x>lim){
return sqrt(m/x);
}
return m/(x*x);
}
il int getSum(ll l,ll r){
ll x=sqrt(m/r),y=sqrt(m/l);
if(x==y){
return (r-l+1)%mod*x%mod;
}
int ret=0;
ret=Mod(ret,(L[y-1]-l)%mod*y%mod);
ret=Mod(ret,(r-L[x]+1)%mod*x%mod);
ret=Mod(ret,Mod(s[y-1],mod-s[x]));
return ret;
}
il int solve(ll x,ll y){
if(!x||!y){
return 0;
}
int t=0;
if(x<=lim){
if(y<x){
t=Mod(t,y*(y+1)/2%mod);
t=Mod(t,(x-y)*y%mod);
}else{
t=Mod(t,x*(x+1)/2%mod);
}
}else{
if(y<lim){
t=Mod(t,y*(y+1)/2%mod);
t=Mod(t,(lim-y)*y%mod);
ll p=L[y];
if(p>=x){
t=Mod(t,(x-lim)%mod*y%mod);
}else{
t=Mod(t,(p-lim)%mod*y%mod);
t=Mod(t,getSum(p+1,x));
}
}else{
t=Mod(t,lim*(lim+1)/2%mod);
t=Mod(t,getSum(lim+1,x));
}
}
return t;
}
void Yorushika(){
read(n,m),lim=myCbrt(m);
rep(i,1,n){
read(a[i]);
}
L[0]=m;
rep(i,1,lim){
L[i]=m/(1ll*(i+1)*(i+1))+1;
s[i]=Mod(s[i-1],(L[i-1]-L[i])%mod*i%mod);
}
rep(i,1,n-1){
if(a[i]<=0||a[i+1]<=0){
continue;
}
if(m/a[i]/a[i+1]<min(a[i],a[i+1])){
puts("0");
return;
}
}
rep(i,1,n){
if(a[i-1]<=0&&a[i]==-1&&a[i+1]<=0){
puts("-1");
return;
}
}
int ans=1;
rep(i,1,n){
if(~a[i]||a[i-1]==-1){
continue;
}
if(a[i+1]!=-1){
ans=1ll*ans*(calc(max(a[i-1],a[i+1]))%mod+1)%mod;
}else{
ll x=calc(a[i-1]),y=calc(a[i+2]);
ans=1ll*ans*Mod(Mod(Mod(solve(x,y),solve(y,x)),mod-min({lim,x,y})),Mod(x%mod,y%mod+1))%mod;
}
}
printf("%d\n",ans);
}
signed main(){
// freopen("tower.in","r",stdin);
// freopen("tower.out","w",stdout);
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7880kb
input:
4 100 -1 7 2 -1
output:
104
result:
ok 1 number(s): "104"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7844kb
input:
4 100 10 -1 -1 1
output:
240
result:
ok 1 number(s): "240"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7756kb
input:
1 0 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7756kb
input:
2 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 8008kb
input:
7 1000 -1 25 0 388 -1 -1 1
output:
14014
result:
ok 1 number(s): "14014"
Test #6:
score: 0
Accepted
time: 0ms
memory: 8012kb
input:
10 1000000 -1 71350 0 6 -1 2 2 -1 -1 358968
output:
652782809
result:
ok 1 number(s): "652782809"
Test #7:
score: 0
Accepted
time: 4ms
memory: 17096kb
input:
7 1000000000000000000 -1 193562447565998153 0 10833 -1 -1 12700
output:
429385005
result:
ok 1 number(s): "429385005"
Test #8:
score: 0
Accepted
time: 0ms
memory: 7884kb
input:
100 1000 -1 174 2 -1 -1 1 2 -1 -1 2 139 -1 -1 1 4 -1 -1 1 1 -1 -1 4 18 -1 -1 356 1 -1 -1 31 1 -1 -1 1 2 -1 -1 1 7 -1 -1 2 0 509 -1 -1 174 0 22 -1 -1 1 1 -1 -1 801 0 2 -1 -1 6 2 -1 -1 1 23 -1 -1 446 0 927 -1 -1 635 1 -1 -1 513 0 5 -1 -1 2 6 -1 -1 2 1 -1 -1 839 0 342 -1 -1 8 1 -1 -1 2
output:
240069117
result:
ok 1 number(s): "240069117"
Test #9:
score: 0
Accepted
time: 0ms
memory: 7884kb
input:
100 1000000 2 -1 -1 257208 1 -1 -1 80 14 -1 -1 20 113 -1 -1 2 155991 -1 -1 1 805463 -1 -1 734 1 -1 -1 942182 0 3 -1 -1 1 1 -1 -1 3 88674 -1 -1 718 0 793 -1 -1 540 1 -1 -1 1 893042 -1 -1 891 0 491 -1 -1 6 18 -1 -1 1 735332 -1 -1 1 1 -1 -1 231702 0 22 -1 -1 1 476 -1 -1 826 20 -1 -1 1 29 -1 -1 2 989 -1...
output:
279593366
result:
ok 1 number(s): "279593366"
Test #10:
score: 0
Accepted
time: 4ms
memory: 19184kb
input:
97 1000000000000000000 -1 55 1 -1 -1 844479880 0 123881535849416001 -1 -1 128083297778537531 1 -1 -1 171572811 0 352900396625380054 -1 -1 1 1 -1 -1 41 6 -1 -1 21627 155 -1 643122694 0 392322295 -1 -1 254987357 2 -1 -1 4 0 571457328786259212 -1 -1 1 8816 -1 -1 131254846109630352 0 971779784498766346 ...
output:
188490398
result:
ok 1 number(s): "188490398"
Test #11:
score: 0
Accepted
time: 24ms
memory: 14156kb
input:
999998 1000 -1 343 1 -1 -1 1 3 -1 -1 1 1 -1 -1 2 0 468 -1 -1 1 1 -1 -1 783 0 5 -1 -1 2 0 760 -1 -1 318 1 -1 -1 1 320 -1 -1 27 1 -1 -1 2 2 -1 -1 2 1 -1 -1 997 1 -1 -1 547 0 313 -1 -1 4 0 304 -1 -1 1 4 -1 -1 980 0 96 -1 -1 1 797 -1 -1 13 0 13 -1 -1 19 0 401 -1 -1 1 1 -1 -1 5 5 -1 -1 26 0 458 -1 -1 6 0...
output:
104236068
result:
ok 1 number(s): "104236068"
Test #12:
score: 0
Accepted
time: 25ms
memory: 14152kb
input:
999998 1000000 -1 538406 1 -1 -1 1 2 -1 -1 288 0 393 -1 -1 256582 0 111893 -1 1 1 -1 -1 105454 0 40 -1 -1 1 4 -1 -1 6 1 -1 -1 3 0 588226 -1 -1 2 22 -1 -1 1 477043 -1 -1 2 912 -1 -1 3 0 539669 -1 -1 1 1 -1 -1 597 0 423 -1 -1 717193 0 506800 -1 -1 424362 0 523732 -1 -1 411789 0 2 -1 -1 2 0 681371 -1 -...
output:
945384981
result:
ok 1 number(s): "945384981"
Test #13:
score: 0
Accepted
time: 40ms
memory: 23268kb
input:
999999 1000000000000000000 34 -1 -1 10403 0 945252394656439232 -1 -1 11 3 -1 -1 2789 153814328 -1 -1 685484514683924741 1 -1 -1 1 14600 -1 -1 162108378 0 942407706831037158 -1 -1 1 81 -1 -1 286801961 1 -1 -1 13177 356030442 -1 -1 9557 0 647686052355282463 -1 -1 797322887 0 33989350 -1 -1 31337243480...
output:
727350500
result:
ok 1 number(s): "727350500"
Test #14:
score: 0
Accepted
time: 0ms
memory: 7756kb
input:
50 1000 -1 -1 -1 694 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 555 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 12ms
memory: 23124kb
input:
1000000 1000000000000000000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
50 1000 210 -1 -1 -1 -1 -1 836 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 517 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 31 -1 128 -1 -1 -1 -1
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 17ms
memory: 22868kb
input:
1000000 1000000000000000000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 0ms
memory: 8012kb
input:
7 100 -1 101 0 1 -1 -1 40
output:
202
result:
ok 1 number(s): "202"
Test #19:
score: 0
Accepted
time: 0ms
memory: 8008kb
input:
17 20 2 -1 -1 2 3 -1 -1 1 3 -1 -1 21 0 5 -1 -1 1
output:
186624
result:
ok 1 number(s): "186624"
Test #20:
score: 0
Accepted
time: 0ms
memory: 7844kb
input:
8 1000000000000 5 -1 -1 2 1 -1 -1 2
output:
667440443
result:
ok 1 number(s): "667440443"
Test #21:
score: 0
Accepted
time: 0ms
memory: 9980kb
input:
4 1000000000000 5 -1 -1 2
output:
709877272
result:
ok 1 number(s): "709877272"
Test #22:
score: 0
Accepted
time: 0ms
memory: 7884kb
input:
4 1000000000000 1 -1 -1 2
output:
232569899
result:
ok 1 number(s): "232569899"