QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181050 | #6346. Record Parity | ucup-team859# | WA | 0ms | 3784kb | C++14 | 1.5kb | 2023-09-16 15:28:06 | 2023-09-16 15:28:06 |
Judging History
answer
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
const int NMAX = 1e6 + 1;
const int MOD = 998244353;
int n;
int aib[NMAX];
int fact[NMAX];
void u(int x) {
for (int i = x; i <= n; i += (i & (-i)))
aib[i] += 1;
}
int q(int x) {
int a = 0;
for (int i = x; i >= 1; i -= (i & (-i)))
a += aib[i];
return a;
}
int lgput(int x, int p) {
int ans = 1, aux = x;
for (int i = 1; i <= p; i <<= 1) {
if (i & p)
ans = 1LL * ans * aux % MOD;
aux = 1LL * aux * aux % MOD;
}
return ans;
}
int invmod(int x) {
return lgput(x, MOD - 2);
}
int c(int n, int k) {
return 1LL * fact[n] * invmod(fact[k]) % MOD * invmod(fact[n - k]) % MOD;
}
void solve() {
int k;
cin >> n >> k;
fact[0] = 1;
for (int i = 1; i <= n; ++i)
fact[i] = fact[i - 1] * 1LL * i % MOD;
stack<int> st;
int nr = 0;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
if (!st.empty() && st.top() >= x) {
while (!st.empty())
st.pop();
}
st.push(x);
if (st.size() >= k) {
nr = nr + c(st.size() - 1, k - 1);
if (nr >= MOD)
nr -= MOD;
}
}
if (k % 2 && nr > 0)
nr = -nr + MOD;
cout << nr << endl;
}
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
5 2 4 1 2 5 3
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
7 3 1 2 3 4 5 6 7
output:
998244318
result:
ok 1 number(s): "998244318"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
5 5 2 5 4 1 3
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3632kb
input:
10 3 9 7 3 6 10 4 8 2 5 1
output:
998244352
result:
wrong answer 1st numbers differ - expected: '0', found: '998244352'