Untitled
unknown
plain_text
a month ago
1.6 kB
13
Indexable
Never
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; // using namespace std; template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define all(x) (x).begin(), (x).end() #define f(i, n) for (int i = 0; i < n; i++) #define trace(x) cerr << #x << ": " << x << '\n' const int N = 20002, mod = 1e9; int C[N][N], fact[N], n, k; void prec() { // O(n^2) for (int i = 0; i < N; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod; } } fact[0] = 1; for (int i = 1; i < N; i++) { fact[i] = 1LL * fact[i - 1] * i % mod; } } int nCr(int n, int r) { // O(1) if (n < r) return 0; return C[n][r]; } int nPr(int n, int r) { // O(1) if (n < r) return 0; return 1LL * nCr(n, r) * fact[r] % mod; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; prec(); vector<int> v(n + 1), dp(n + 1, 0ll); for (int i = 1; i <= n; i++) cin >> v[i]; ll ans = 0; o_set<int> se; for (int i = 1; i <= n; i++) { int big = 0; big=i-1-(se.order_of_key(v[i])); // for (int j = 1; j < i; j++) // { // big += v[j] > v[i]; // } if (big >= k - 1) ans += nCr(big, k - 1); if (ans >= mod) ans -= mod; se.insert(v[i]); } cout << ans << "\n"; }
Leave a Comment