QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #584630 | #6410. Classical DP Problem | liuhengxi | WA | 0ms | 1604kb | C++14 | 1.2kb | 2024-09-23 15:56:39 | 2024-09-23 15:56:39 |
Judging History
answer
// created: 2024-09-23 15:49:11
#include<cstdio>
#include<cctype>
#include<algorithm>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
bool neg=false;int c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
typedef unsigned long long ull;
constexpr int N=5005,MOD=998244353;
int n,m,f[N];
int solve(const int *a)
{
int k=a[m];
F(i,0,k+1)f[i]=0;
f[0]=1;
F(i,0,m)
{
for(int j=min(i+1,k);j;--j)f[j]=(int)(((ull)(k-j+1)*f[j-1]+(ull)(a[i]-k+j)*f[j])%MOD);
f[0]=(int)((ull)(a[i]-k)*f[0]%MOD);
}
return f[k];
}
int a[N],b[N];
int main()
{
read(n);
F(i,0,n)++b[read(a[n-1-i])-1];
for(int i=n;~--i;)b[i]+=b[i+1];
while(a[m]>m)++m;
ull fac=1;
F(i,1,m+1)(fac*=i)%=MOD;
ull ans=solve(a)+solve(b)+MOD-fac;
ans%=MOD;
printf("%d %d\n",m,(int)ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1496kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1520kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1508kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 1544kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 1508kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 1512kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 0ms
memory: 1524kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 0ms
memory: 1528kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: 0
Accepted
time: 0ms
memory: 1604kb
input:
10 2 4 5 5 5 5 6 8 8 10
output:
5 864
result:
ok 2 number(s): "5 864"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 1600kb
input:
30 6 8 9 9 9 10 13 14 15 15 16 17 17 18 20 22 22 23 23 24 24 25 25 25 27 28 28 29 29 30
output:
17 618007537
result:
wrong answer 2nd numbers differ - expected: '986189864', found: '618007537'