QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#37055#1284. Partition NumberNaCly_FishWA 813ms20160kbC++2.2kb2022-06-30 09:56:342022-06-30 09:56:35

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:56:35]
  • 评测
  • 测评结果:WA
  • 用时:813ms
  • 内存:20160kb
  • [2022-06-30 09:56:34]
  • 提交

answer

#pragma GCC optimize (2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define N 650003
#define ll long long
#define reg register
#define p 1000000007
#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 (3ll*x*x-x)>>1;
}

int T,n,m,tmp,len,sum,ans;
int f[N],g[N],a[N];
coef h[N],_h[N];
ll sup,t;

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) continue;
                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: 801ms
memory: 20160kb

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: 0
Accepted
time: 813ms
memory: 18180kb

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:

656513071
370664764
307269426
290963116
49499707
470710
612150225
330845525
873165144
948675759
659641122
968862177
64639712
328389177
408917220
4498768
640121836
656874091
378916100
635314832
495592694
366885137
89776883
143643404
419554963
926186762
98591876
493963833
801434574
773303382
384230433...

result:

ok 500 tokens

Test #3:

score: -100
Wrong Answer
time: 802ms
memory: 18180kb

input:

100
9 1772
834 532 435 1280 1656 258 1125 1428 1081
4 1378
109 959 683 1359
5 1404
343 99 582 1314 1158
5 1732
343 88 1518 383 888
1 1649
809
3 2148
529 398 1274
9 1498
1149 1100 753 1438 1023 781 1382 174 812
5 1974
1672 1049 946 556 1368
3 1841
1126 778 1203
8 2823
1492 1855 59 1955 2160 1733 132 ...

output:

337901251
92194599
724015244
956239082
302019412
406401766
344249249
479624994
755799589
665478883
829882337
870185928
158625521
151656158
153754980
656712357
376024919
799731771
627915771
42105045
764310042
734330711
22153723
616632794
753088730
727367604
240794329
455175449
121526220
549167830
313...

result:

wrong answer 47th words differ - expected: '924066570', found: '44044517'