3 条题解
-
0
设 表示前 个人有 个逆序对,则显然有:
使用前缀和优化就好,时间复杂度
#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 */ -
-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];然后 那一层循环使用前缀和优化一下就行了。
#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
- 上传者