QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#670109#7875. Queue SortingwzxtslAC ✓154ms6536kbC++231.9kb2024-10-23 20:31:062024-10-23 20:31:07

Judging History

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

  • [2024-10-23 20:31:07]
  • 评测
  • 测评结果:AC
  • 用时:154ms
  • 内存:6536kb
  • [2024-10-23 20:31:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
const int mod = 998244353;
const double eps = 1e-9;
const int N=1007;
int n,m;
int a[N];
long long f[N], g[N],inv[N];
int sum[N];
int dp[N][N];
long long p = 998244353;
long long qpow(long long a, long long n)
{
    long long result = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            result = result * a % p;
        }
        a = a * a % p;
        n >>= 1;
    }
    return result % p;
}
void init()
{
	int n=1000;
    f[0] = g[0] = 1;
    inv[1]=inv[0]=1;
    //for(int i=2;i<=n;i++){
        //inv[i]=inv[p%i]*(p-p/i)%p;//线性筛求逆元
    //}
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] * i % p;
    }
    g[n-1]=qpow(f[n-1],p-2);
    for(int i=n-2;i>=0;i--){
        g[i]=g[i+1]*(i+1)%p;
    }
}
long long C(long long n, long long m)
{
    return (f[n] * g[m]) % p * g[n - m] % p;
}
void solve(){
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
        cin>>a[i];
		sum[i]=sum[i-1]+a[i];
    }
	dp[0][0]=1;
    for(int i=0;i<n;i++){
		for(int j=0;j<=sum[i];j++){
			if(dp[i][j]){
				dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
				for(int k=j+1;k<sum[i+1];k++){
					int lb=max(0ll,a[i+1]-(k-j));
					int ub=min(a[i+1]-1,sum[i+1]-k-1);
					for(int x=lb;x<=ub;x++){
						dp[i+1][k]=(dp[i+1][k]+dp[i][j]*C(k-j-1,a[i+1]-x-1)%mod)%mod;
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<sum[n];i++){
		ans=(ans+dp[n][i])%mod;
	}
	cout<<ans<<endl;
}
signed main(){
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 145ms
memory: 5364kb

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: 154ms
memory: 6536kb

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: 140ms
memory: 4776kb

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: 31ms
memory: 4144kb

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: 3576kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 2ms
memory: 5656kb

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: 3672kb

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: 1ms
memory: 3776kb

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: 3776kb

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: 3740kb

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: 34ms
memory: 5124kb

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: 3636kb

input:

2
232 268

output:

929717758

result:

ok 1 number(s): "929717758"

Test #14:

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

input:

1
500

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 61ms
memory: 3692kb

input:

3
155 180 165

output:

911108550

result:

ok 1 number(s): "911108550"

Extra Test:

score: 0
Extra Test Passed