QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116618#6410. Classical DP ProblemLiuxizaiWA 1ms5568kbC++142.1kb2023-06-29 16:59:512023-06-29 16:59:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 16:59:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5568kb
  • [2023-06-29 16:59:51]
  • 提交

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'