QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#883698 | #7875. Queue Sorting | wanggk | AC ✓ | 86ms | 5376kb | C++14 | 2.3kb | 2025-02-05 18:11:58 | 2025-02-05 18:11:59 |
Judging History
answer
/*
* @Author: wanggk
* @Date: 2025-02-05 16:19:34
* No surrender, no illusions
* And for better or worse
*/
#include<bits/stdc++.h>
#define Spc putchar(' ')
#define End putchar('\n')
#define For(i,il,ir) for(int i=(il);i<=(ir);++i)
#define Fr(i,il,ir) for(int i=(il);i<(ir);++i)
#define Forr(i,ir,il) for(int i=(ir);i>=(il);--i)
#define ForE(u) for(int i=head[u];~i;i=e[i].nxt)
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
namespace _TvT_{
template<typename T>
inline void rd(T& x){
bool f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=1; ch=getchar(); }
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f) x=-x;
}
template<typename T,typename... Args>
void rd(T& first,Args&... args){ rd(first),rd(args...); }
int write_num[50];
template<typename T>
inline void write(T x){
int len=0;
if(x<0) putchar('-'),x=-x;
do write_num[len++]=x%10ll; while(x/=10ll);
while(len--) putchar(write_num[len]+'0');
}
template<typename T,typename... Args>
void write(T first,Args... args){ write(first),Spc,write(args...); }
}using namespace _TvT_;
const ll mod=998244353;
const int maxn=505;
void qadd(ll &x,ll y){ x=(x+y>=mod)?x+y-mod:x+y; }
int n;
int a[maxn],sum;
ll f[maxn][maxn],fac[maxn],inv[maxn];
ll qp(ll x,ll b){ ll res=1ll; x%=mod; for(;b;x=x*x%mod,b>>=1) if(b&1) res=res*x%mod; return res; }
ll C(int x,int y){ return (x<y||x<0||y<0)?0:fac[x]*inv[y]%mod*inv[x-y]%mod; }
signed main()
{
const int N=500;
fac[0]=1;For(i,1,N) fac[i]=fac[i-1]*(ll)i%mod;
inv[N]=qp(fac[N],mod-2);Forr(i,N-1,0) inv[i]=inv[i+1]*(i+1)%mod;
rd(n);
For(i,1,n) rd(a[i]),sum+=a[i];
f[n+1][1]=1;
Forr(i,n,1) For(j,1,sum+1) if(f[i+1][j])
{
qadd(f[i][j+a[i]],f[i+1][j]); // lft=0
For(lft,1,a[i])
{
int front=a[i]-lft;
For(k,2,j){
int num=j-k+1;
ll tmp=C(num+(lft-1)-1,lft-1);
qadd(f[i][k+front],f[i+1][j]*tmp%mod);
}
}
}
ll res=0;
// For(j,1,sum+1) write(f[1][j]),Spc; End;
For(j,1,sum+1) qadd(res,f[1][j]);
write(res),End;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 0
Accepted
time: 85ms
memory: 4736kb
input:
300 0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...
output:
507010274
result:
ok 1 number(s): "507010274"
Test #3:
score: 0
Accepted
time: 86ms
memory: 5376kb
input:
500 1 1 0 2 1 0 2 3 2 0 0 2 0 2 1 1 0 0 1 1 1 2 1 1 1 0 1 1 2 2 1 4 0 2 1 0 2 3 1 0 1 1 0 2 1 2 2 1 0 0 3 1 4 1 1 2 1 1 0 1 3 1 2 0 0 0 2 1 2 0 0 3 2 1 1 1 1 1 2 1 0 1 0 0 0 1 0 0 2 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 2 1 1 0 1 1 0 1 1 0 0 1 0 3 1 3 0 0 2 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 ...
output:
7590964
result:
ok 1 number(s): "7590964"
Test #4:
score: 0
Accepted
time: 85ms
memory: 4352kb
input:
200 3 1 0 3 2 1 0 3 1 1 2 3 3 1 6 2 1 3 2 1 1 2 1 2 1 5 2 2 3 4 0 4 2 1 2 2 0 2 3 1 2 3 6 3 2 3 2 2 4 2 7 2 1 5 1 9 0 4 4 8 3 3 3 1 3 0 2 2 8 1 3 5 4 3 0 6 1 6 1 3 4 2 2 1 1 4 4 4 1 0 4 3 4 3 3 0 3 2 0 0 3 4 0 3 1 3 2 4 3 2 0 3 2 2 3 2 2 2 1 2 2 1 0 2 0 3 1 3 5 1 3 3 6 5 3 2 2 2 3 6 2 0 5 2 2 2 2 1 ...
output:
507844569
result:
ok 1 number(s): "507844569"
Test #5:
score: 0
Accepted
time: 19ms
memory: 3712kb
input:
100 4 8 2 5 4 4 3 0 2 7 2 3 4 4 1 2 3 4 4 4 3 3 3 3 3 2 4 1 3 5 5 1 4 6 1 1 1 3 2 3 2 1 0 1 4 4 2 4 2 5 3 5 1 6 2 3 3 1 4 4 4 1 4 4 3 4 2 0 2 3 6 1 3 3 5 4 1 1 2 3 0 3 2 2 1 3 3 2 5 6 3 2 3 3 5 4 2 3 4 4
output:
989550242
result:
ok 1 number(s): "989550242"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5376kb
input:
500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 2 1 3 3 2 3 1 1 3 1
output:
165452340
result:
ok 1 number(s): "165452340"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
20 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0
output:
2
result:
ok 1 number(s): "2"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
20 0 0 1 0 0 0 0 1 0 0 0 0 0 0 2 0 1 0 0 0
output:
28
result:
ok 1 number(s): "28"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 1 1 1 1 1 1 1 1 1 1
output:
16796
result:
ok 1 number(s): "16796"
Test #12:
score: 0
Accepted
time: 20ms
memory: 4736kb
input:
300 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
431279497
result:
ok 1 number(s): "431279497"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
2 232 268
output:
929717758
result:
ok 1 number(s): "929717758"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 500
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 37ms
memory: 3584kb
input:
3 155 180 165
output:
911108550
result:
ok 1 number(s): "911108550"
Extra Test:
score: 0
Extra Test Passed