結果
問題 | No.1621 Sequence Inversions |
ユーザー |
![]() |
提出日時 | 2021-07-22 22:04:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,938 ms / 3,000 ms |
コード長 | 1,122 bytes |
コンパイル時間 | 4,142 ms |
コンパイル使用メモリ | 261,840 KB |
最終ジャッジ日時 | 2025-01-23 06:45:15 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001mint memo[101][101][5001];bool v[101][101][5001];mint get(int x,int t,int k){if(x<0){if(t!=0||k!=0)return 0;return 1;}if(v[x][t][k])return memo[x][t][k];v[x][t][k] = true;mint ret = 0;rep(i,t+1){if(i*x>k)break;ret += get(x-1,t-i,k-i*x);}memo[x][t][k] = ret;return ret;}int main(){int N,K;cin>>N>>K;vector<int> A(N);vector<int> t;rep(i,N){cin>>A[i];t.push_back(A[i]);}sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());vector<int> cnt(t.size(),0);rep(i,N){int d = distance(t.begin(),lower_bound(t.begin(),t.end(),A[i]));cnt[d] ++;}vector<mint> dp(K+1,0);dp[0] = 1;int sum = 0;rep(i,t.size()){vector<mint> ndp(K+1,0);rep(j,K+1){ndp[j] = get(sum,cnt[i],j);}sum += cnt[i];dp = convolution(dp,ndp);while(dp.size()>K+1)dp.pop_back();}cout<<dp[K].val()<<endl;return 0;}