QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#37046 | #1284. Partition Number | NaCly_Fish | WA | 759ms | 19020kb | C++ | 2.2kb | 2022-06-30 09:48:49 | 2022-06-30 09:48:52 |
Judging History
answer
#pragma GCC optimize (2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define N 600003
#define ll long long
#define reg register
#define p 998244353
#define pi 3.141592653589793
using namespace std;
inline void read(int &x){
x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c^48);
c = getchar();
}
}
struct coef{
int v,t;
inline coef(int _v=0,int _t=0):v(_v),t(_t){}
inline bool operator < (const coef& rhs) const{
return t < rhs.t;
}
};
inline int omega(int x){
return (3*x*x-x)>>1;
}
int T,n,m,t,tmp,len,sum,ans;
int f[N],g[N],a[N];
coef h[N],_h[N];
ll sup;
int main(){
scanf("%d",&T);
m = 300000;
for(int i=1;omega(i)<=m;i++){
g[t++] = omega(i);
g[t++] = omega(-i);
}
f[0] = 1;
for(int i=1;i<=m;i++){
for(int j=0;j<t&&g[j]<=i;j++)
f[i] = (f[i]+(ll)(((j>>1)&1)?-1:1)*f[i-g[j]])%p;
}
while(T--){
scanf("%d%d",&n,&m);
sup = (ll)m*(m+1)>>1;
t = 0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
t += a[i];
}
if(sup-t<m){
puts("0");
continue;
}
h[0] = coef(1,0);
h[1] = coef(-1,a[1]);
len = 1;
for(int i=2;i<=n;++i){
tmp = len;
for(int j=0;j<=tmp;++j){
if(h[j].t+a[i]>m) break;
h[++len] = coef(-h[j].v,h[j].t+a[i]);
}
sort(h,h+len+1);
tmp = 0;
for(int j=0,k=0;;j=k){
sum = 0;
while(h[j].t==h[k].t){
sum = (sum+h[k].v)%p;
++k;
}
_h[tmp++] = coef(sum,h[j].t);
if(k>len) break;
}
len = tmp-1;
for(int j=0;j<=len;++j) h[j] = _h[j];
}
ans = 0;
for(int i=0;i<=len&&h[i].t<=m;++i)
ans = (ans+(ll)h[i].v*f[m-h[i].t])%p;
printf("%d\n",(ans+p)%p);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 751ms
memory: 19020kb
input:
5 1 4 1 1 4 2 1 4 3 3 4 1 2 3 4 4 1 2 3 4
output:
2 3 4 1 0
result:
ok 5 tokens
Test #2:
score: -100
Wrong Answer
time: 759ms
memory: 18992kb
input:
500 1 2921 832 1 1952 1842 1 1890 1711 1 2710 2136 1 1420 118 1 1427 921 1 1436 1346 1 1099 676 1 1146 75 1 1993 963 1 2819 34 1 1830 19 1 2900 1912 1 1070 993 1 2114 1434 1 2115 457 1 1407 888 1 1374 98 1 1450 555 1 2740 1469 1 2983 490 1 2209 418 1 2698 2671 1 2653 734 1 1707 1674 1 1247 527 1 147...
output:
534331308 826778795 787427970 116335786 656062179 132106757 17765543 361375797 643194883 887975470 921626129 436755061 876475876 630746069 905154023 431660970 382678132 532407817 371248392 204496571 699064370 569327593 744812919 782114486 75271714 966181965 377593956 964450666 952326515 726080378 45...
result:
wrong answer 1st words differ - expected: '656513071', found: '534331308'