QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#883698#7875. Queue SortingwanggkAC ✓86ms5376kbC++142.3kb2025-02-05 18:11:582025-02-05 18:11:59

Judging History

This is the latest submission verdict.

  • [2025-02-05 18:11:59]
  • Judged
  • Verdict: AC
  • Time: 86ms
  • Memory: 5376kb
  • [2025-02-05 18:11:58]
  • Submitted

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,我给组数据试试?

详细

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