QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661033#9436. Some Sum of SubsetForever_Young#WA 1ms3948kbC++141006b2024-10-20 14:25:192024-10-20 14:25:22

Judging History

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

  • [2024-10-20 14:25:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3948kb
  • [2024-10-20 14:25:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int ans[3030],dp[3030],n,m,a[3030],fac[3030],ifac[3030];
const int mo=998244353;
int pow(int x,int y){
    int res=1;
    while (y){
        if (y&1) res=1ll*res*x%mo;
        x=1ll*x*x%mo;
        y=y/2;
    }
    return res;
}
int c(int x,int y){//x<=y
    return 1ll*ifac[x]*ifac[y-x]%mo*fac[y]%mo;
}
int main(){
    scanf("%d%d",&n,&m);
    fac[0]=1;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        fac[i]=1ll*i*fac[i-1]%mo;
    }
    ifac[n]=pow(fac[n],mo-2);
    for (int i=n;i;i--){
        ifac[i-1]=1ll*i*ifac[i]%mo;
    }
    sort(a+1,a+n+1);
    dp[0]=1;
    for (int i=n;i;i--){
        int tmp=0;
        for (int j=m;j>=m-a[i];j--)
            tmp=(tmp+dp[j])%mo;
        for (int j=0;j<i;j++)
            ans[j]=(ans[j]+1ll*tmp*c(j,i-1))%mo;
        for (int j=m;j>=0;j--)
            dp[min(m,j+a[i])]=(dp[min(m,j+a[i])]+dp[j])%mo;
    }
    for (int i=0;i<=n;i++) printf("%d\n",ans[i]);
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3948kb

input:

4 7
3 1 5 2

output:

6
4
1
0
0

result:

ok 5 tokens

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3824kb

input:

1 5
7

output:

7
0

result:

wrong answer 1st words differ - expected: '1', found: '7'