QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116618 | #6410. Classical DP Problem | Liuxizai | WA | 1ms | 5568kb | C++14 | 2.1kb | 2023-06-29 16:59:51 | 2023-06-29 16:59:53 |
Judging History
answer
#include<bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
T n = 0; int f = 1; char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch)){
n = n * 10 + ch - '0';
ch = getchar();
}
return f * n;
}
template<typename T>
void write(T n){
if(n/10) write(n/10);
putchar(n%10+'0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types&... args){
arg = read<Type>();
input(args...);
}
namespace Main{
const int N = 5005;
const int MOD = 998244353;
int n, k, a[N], b[N];
ll f[N][N];
void solve(int x){
f[0][0] = 1;
for(int i = 1; i <= k; i++){
for(int j = 0; j <= i && j <= x; j++){
f[i][j] = f[i - 1][j] * (a[n - i + 1] - x + j) % MOD;
if(j) f[i][j] = (f[i][j] + f[i - 1][j - 1] * (x - j + 1)) % MOD;
}
}
}
void Main(){
input(n);
for(int i = 1; i <= n; i++) input(a[i]);
k = 0;
for(int i = n; i >= 1; i--){
if(a[i] >= n - i + 1) k = n - i + 1;
else break;
}
ll ans = -1;
for(int i = 1; i <= k; i++) ans = ans * i % MOD;
solve(a[n - k]);
ans = (ans + f[k][a[n - k]]) % MOD;
int mx = a[n];
for(int i = 1; i <= mx; i++){
for(int j = n; j >= 1; j--){
if(a[j] >= i) b[i]++;
else break;
}
}
for(int i = 1; i <= mx; i++) a[i] = b[mx - i + 1];
solve(a[mx - k]);
ans = (ans + f[k][a[mx - k]]) % MOD;
write(k), putchar(' '), write(ans);
return;
}
} // namespace
int main(){
#ifdef Liuxizai
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif // Liuxizai
Main::Main();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3280kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5568kb
input:
2 1 1
output:
1 1
result:
wrong answer 2nd numbers differ - expected: '2', found: '1'