QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#145331#6410. Classical DP ProblemInsert_Username_HereWA 1ms3644kbC++201.2kb2023-08-22 07:46:222023-08-22 07:46:23

Judging History

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

  • [2023-08-22 07:46:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3644kb
  • [2023-08-22 07:46:22]
  • 提交

answer

#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 998244353;
// Cope Counter = at least 109

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
  ll n;
  cin >> n;
  ll arr[n + 1][2], dp[n][n];
  ll smax = 0, c = 1;
  arr[0][0] = arr[0][1] = 0;
  for(ll i = n; i > 0; i--) {
    cin >> arr[i][0];
    for(; c <= arr[i][0]; c++) arr[c][1] = i;
    smax = max(smax, min(i + 1, arr[i][0]));
  }
  for(; c <= n; c++) arr[c][1] = 0;
  for(ll i = 0; i <= n; i++) {
    for(ll j = 0; j <= n; j++) dp[i][j] = 0;
  }
  dp[0][0] = 1;
  ll fact = 1, ans = 0;
  for(ll i = 2; i <= smax; i++) fact = fact * i % mod;
  if(smax == n) {
    cout << n << " " << fact << "\n";
    return 0;
  }
  for(ll bk = 0; bk < 2; bk++) {
    for(ll i = 1; i <= smax; i++) {
      for(ll j = 0; j <= i; j++) {
        dp[i][j] = dp[i - 1][j] + arr[i][bk] - arr[smax + 1][bk] + j;
        if(j > 0) dp[i][j] += dp[i - 1][j - 1] + arr[smax + 1][bk] - j - 1;
        dp[i][j] %= mod;
      }
    }
    ans = (ans + dp[smax][arr[smax + 1][bk]]) % mod;
  }
  cout << smax << " " << (ans - fact + mod) % mod << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3584kb

input:

2
2 2

output:

2 2

result:

wrong answer 2nd numbers differ - expected: '6', found: '2'