QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#37046#1284. Partition NumberNaCly_FishWA 759ms19020kbC++2.2kb2022-06-30 09:48:492022-06-30 09:48:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-30 09:48:52]
  • 评测
  • 测评结果:WA
  • 用时:759ms
  • 内存:19020kb
  • [2022-06-30 09:48:49]
  • 提交

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;
}

详细

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'