3 条题解

  • -1
    @ 2025-11-7 14:37:20

    这不是最优解,@ 会 O(nn)\mathcal O(n\sqrt n)。但我还不会,一下是 O(n2)\mathcal O(n^2) 做法。

    题目说 hih_i 两两不同,所以 hih_i 具体是多少我们不关心。

    所以要求出有 mm 个逆序对且长度为 nn 的排列的方案数。

    本题 n≤1000n\le 1000,考虑 O(n2)\mathcal O(n^2) 的做法。

    设计 dpi,jdp_{i,j} 表示前 ii 个数,有 jj 个逆序对的方案数。第 ii 个数产生的逆序对数量是 [0,i−1][0,i-1]。我们首先写朴素转移:

    	dp[0][0]=1;
    	for(int i=1; i<=n; ++i) {
    		for(int j=1;j<=m;++j){
    			for(int k=0; k<i&&k<=j; ++k) {
    				dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;
    			}
    		}
    	}
    	cout<<dp[n][m];
    

    然后 kk 那一层循环使用前缀和优化一下就行了。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=1005;
    int n,m,mod,dp[N][N],sum[N][N];
    signed main() {
    	cin>>n>>m>>mod;
    	dp[0][0]=1;
    	for(int i=1; i<=n; ++i) {
    		sum[i-1][0]=dp[i-1][0];
    		for(int j=1; j<=m; ++j) sum[i-1][j]=(sum[i-1][j-1]+dp[i-1][j])%mod;
    		for(int j=0; j<=m; ++j)	dp[i][j]=(dp[i][j]+sum[i-1][j]-sum[i-1][j-min(j,i-1)-1]+mod)%mod;
    	}
    	cout<<dp[n][m];
    	return 0;
    }
    

    信息

    ID
    575
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    (无)
    递交数
    95
    已通过
    1
    上传者