3 条题解

  • 0
    @ 2025-11-7 15:15:51

    设 dpi,jdp_{i,j} 表示前 ii 个人有 jj 个逆序对,则显然有:

    dpi,j=∑k=0i−1dpi−1,j−kdp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}

    使用前缀和优化就好,时间复杂度 O(n2)O(n^2)

    #include<algorithm>
    #include<iostream>
    #include<cstdio>
    #define int long long
    using namespace std;
    bool Test_MLE_start;
    constexpr int N=1005;
    int _=1,n,m,mod,a[N],dp[N][N],sum[N][N];
    inline int reads(){
    	int c=getchar(),x=0,f=1;
    	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    	return x*f;
    }inline void files(){
    	freopen("A.in","r",stdin);
    //	freopen("std.out","w",stdout);
    }inline void clr(){
    //	Don't forget!
    
    }
    int calc(int x){return x*(x+1)/2;}
    bool Test_MLE_end;
    signed main(){
    //	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
    //	files();
    //	_=reads();
    	while(_--){
    		clr();n=reads(),m=reads(),mod=reads();
    		for(int i=1;i<=n;i++) a[i]=reads();
    		sort(a+1,a+n+1);dp[1][0]=sum[1][0]=1;
    		for(int i=1;i<=m;i++) sum[1][i]=(sum[1][i-1]+dp[1][i])%mod;
    		for(int i=2;i<=n;i++){
    			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;
    				sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
    			}
    		}printf("%lld\n",dp[n][m]);
    	}return 0;
    }
    
    /*
    3 2 233
    12 34 5
    
    */
    
    • 0
      @ 2025-11-7 14:32:48

      考虑设状态,设 fi,jf_{i,j} 表示一个 1∼i1\sim i 且有 jj 个逆序对的排列有多少个,转移显然:

      fi,j=∑k=0i−1fi−1,j−kf_{i,j}=\sum_{k=0}^{i-1}f_{i-1,j-k}

      前缀和优化一下做完了,时间复杂度 O(n2)O(n^2)。

      • -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;
        }
        
        • 1

        信息

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