QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#886416#2874. First to Solveleo020630WA 3ms9228kbC++202.7kb2025-02-07 02:16:472025-02-07 02:16:47

Judging History

This is the latest submission verdict.

  • [2025-02-07 02:16:47]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 9228kb
  • [2025-02-07 02:16:47]
  • Submitted

answer

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll mod = 998244353;

ll po(ll x,ll y)
{
    ll a=1;
    while(y>0)
    {
        if(y%2) a=a*x%mod;
        x=x*x%mod; y/=2;
    }
    return a;
}

ll F[505],iF[505];

ll A[505][30];

ll dp1[30][30][305],dp2[30][305];

ll P[505][30][305],prod[30][305];
ll cnt[505];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    ll n,m,k; cin>>n>>m>>k;

    F[0]=1;
    for(ll i=1;i<=500;i++) F[i]=F[i-1]*i%mod;
    iF[500]=po(F[500],mod-2);
    for(ll i=499;i>=0;i--) iF[i]=(i+1)*iF[i+1]%mod;

    for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin>>A[i][j], cnt[i]+=!!A[i][j];

    for(ll x=1;x<=n;x++)
    {
        memset(dp1,0,sizeof(dp1));
        dp1[0][0][0]=1;

        for(ll i=1;i<=m;i++)
        {
            for(ll j=0;j<=m;j++) for(ll t=0;t<=k;t++)
            {
                dp1[i][j][t]=dp1[i-1][j][t];
                if(A[x][i]!=0 && t>=A[x][i])
                    dp1[i][j][t]+=dp1[i-1][j-1][t-A[x][i]]*F[j]%mod, dp1[i][j][t]%=mod;
            }
        }
        for(ll i=1;i<=m;i++)
        {
            if(A[x][i]==0)
            {
                P[x][i][k+1]=1;
                continue;
            }
            memset(dp2,0,sizeof(dp2));
            dp2[0][0]=1;
            P[x][i][A[x][i]]=iF[cnt[x]]*F[cnt[x]-1]%mod;
            //cout<<i<<"?\n";
            for(ll j=1;j<=m;j++) for(ll t=0;t<=k;t++)
            {
                if(t>=A[x][i]) dp2[j][t]=(dp1[m][j][t]-dp2[j-1][t-A[x][i]]*F[j]%mod+mod)%mod;
                else dp2[j][t]=dp1[m][j][t];
                if(t+A[x][i]<=k)
                    P[x][i][t+A[x][i]]=(P[x][i][t+A[x][i]]+dp2[j][t]*iF[cnt[x]]%mod*F[cnt[x]-j-1]%mod)%mod;
            }

            ll tot=0;
            for(ll t=0;t<=k;t++) tot=(tot+P[x][i][t])%mod;
            P[x][i][k+1]=(mod+1-tot)%mod;

        }
        for(ll i=1;i<=m;i++) for(ll t=k;t>=0;t--) P[x][i][t]+=P[x][i][t+1], P[x][i][t]%=mod;


        //for(ll i=1;i<=m;i++) for(ll t=0;t<=k+1;t++) if(P[x][i][t]!=0) cout<<"["<<x<<' '<<i<<' '<<t<<' '<<P[x][i][t]<<"]\n";

    }
    for(ll i=1;i<=m;i++)
    {
        for(ll j=0;j<=k+1;j++)
        {
            prod[i][j]=1;
            for(ll x=1;x<=n;x++) prod[i][j]*=P[x][i][j], prod[i][j]%=mod;
        }
    }

    for(ll i=1;i<=n;i++)
    {
        ll ans=0;
        for(ll j=1;j<=m;j++)
        {
            if(A[i][j]==0) continue;
            for(ll t=0;t<=k;t++) ans+=prod[j][t]*po(P[i][j][t],mod-2)%mod*(P[i][j][t]-P[i][j][t+1]+mod)%mod, ans%=mod;
        }
        cout<<ans<<'\n';
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7832kb

input:

5 3 60
30 0 0
40 20 0
30 60 0
0 0 0
60 60 1

output:

1
1
249561089
0
499122177

result:

ok 5 number(s): "1 1 249561089 0 499122177"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7276kb

input:

1 1 1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 6256kb

input:

1 1 1
0

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 1ms
memory: 9228kb

input:

5 5 10
0 4 5 6 0
0 7 10 2 5
2 0 5 5 0
1 0 4 8 1
2 2 8 7 2

output:

53696073
326278016
117193580
610846980
22645359

result:

ok 5 number(s): "53696073 326278016 117193580 610846980 22645359"

Test #5:

score: -100
Wrong Answer
time: 3ms
memory: 8880kb

input:

10 15 100
42 52 40 31 0 23 31 39 2 33 99 49 36 84 84
97 67 79 9 24 91 97 29 67 31 44 67 32 48 21
82 91 72 64 21 29 44 55 35 100 80 47 51 55 1
17 5 93 13 30 21 35 9 78 2 36 33 87 84 0
34 84 71 60 34 19 0 26 61 54 53 33 0 93 69
8 8 74 10 0 10 71 20 94 19 51 27 12 40 10
24 0 3 0 63 45 60 9 39 81 92 100...

output:

244569270
842871238
184290502
544622396
706071573
147417856
858367844
770716509
526507063
990388850

result:

wrong answer 1st numbers differ - expected: '150531227', found: '244569270'