yukicoder : No.1621 Sequence Inversions

★3.5位でもいい気がする。
https://yukicoder.me/problems/no/1621

問題

N要素の整数列Aが与えられる。
Aを並べ替えた数列Bのうち、転倒数がKとなるのは何通りか。

解法

A中で同じ値のものごとにまとめて処理しよう。

f(n,k) := A中で(重複を除き)n番目までに大きいものの並び順を考えたとき、転倒数がkとなるものの組み合わせ
とするとき、f(n,k)からf(n+1,*)への寄与を考える。

n番目までに大きい要素がx個、(n+1)番目に大きい要素がy個あるとき、挿入DPの要領で、この(x+y)個を並べ、転倒数ごとの組み合わせを数え上げて行こう。

int N,K;
int A[101];
ll from[10101];

ll dp[5100][101][101];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	map<int,int> M;
	FOR(i,N) {
		cin>>x;
		M[-x]++;
	}
	int cur=0;
	from[0]=1;
	FORR2(e,n,M) {
		k=(cur+n)*(cur+n+1)/2+1;
		FOR(x,k) {
			FOR(i,cur+1) FOR(j,n+1) dp[x][i][j]=0;
			dp[x][0][0]=from[x];
		}
		FOR(x,5051) {
			FOR(i,cur+1) FOR(j,n+1) if(dp[x][i][j]) {
				if(i<cur) (dp[x][i+1][j]+=dp[x][i][j])%=mo;
				if(j<n) (dp[x+i][i][j+1]+=dp[x][i][j])%=mo;
			}
		}
		FOR(x,k) from[x]=dp[x][cur][n];
		cur+=n;
	}
	cout<<from[K]<<endl;
}

まとめ

同じ値がない場合だと、O(1)とかO(N)で数えられたりしないかな、どうだろ。