QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#886416 | #2874. First to Solve | leo020630 | WA | 3ms | 9228kb | C++20 | 2.7kb | 2025-02-07 02:16:47 | 2025-02-07 02:16:47 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'