一道很良心的省选题。
我们先考虑如何优雅的骗分。
有30%的程序精度要求K<=3,这个时候我们只要把题目给你的那个程序拿下来改一改就好了。
RP不差的话有30分。
我们再观察一波数据，发现N<=10时我们可以暴力枚举所有可能，除以N！求概率。
来一发50分代码（为了稳健，没播种子）
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define SIZ 5000000 #define abs(t) (t)>0?(t):-(t) using namespace std; int a[107],gg[11],p[11],usd[11],tot,ot; int n,s,t,m,GG,k,anss,ans; void dfs(int x){ if (x==n+1) {if (anss>=m) ans++; return;} for (int i=1;i<=n;i++) if (!usd[i]) { usd[i]=1; p[x]=i; anss+=abs(i-p[x-1]); dfs(x+1); anss-=abs(i-p[x-1]); usd[i]=0; } } void out(long double xx,int g){ if (g==-1) { printf("%d",(int)xx); return; } printf("%d.",(int)xx); xx=xx*10; while (g--) { printf("%d",(int)xx); xx=xx*10-((int)xx)*10; } xx=xx*10; GG=(int)xx; if (GG%10<4) GG=GG/10; else GG=GG/10+1; printf("%d",GG); } void Out(int x,int y,int g){ if (g==-1) { if (x*2>=y) printf("1 "); else printf("0 "); return; } printf("%d.",x/y); x=x%y*10; while (g--) { printf("%d",x/y); x=x%y*10; } GG=x/y; ot=x%y; if (ot*2>=y) GG++; printf("%d",GG); } int main () { scanf("%d%d%d",&n,&m,&k); if (n<=10){ for (int i=1;i<=n;i++) { anss=0; p[1]=i; usd[i]=1; dfs(2); usd[i]=0; } tot=1; for (int i=1;i<=n;i++) tot=tot*i; Out(ans,tot,k-1); return 0; } for (int i=1;i<n;i++) a[i]=i; s=0; for (int i=0; i<SIZ; i++) { random_shuffle(a,a+n); t=0; for (int j=0; j<n-1; j++) t+=abs(a[j+1]-a[j]); if (t>=m) s++; } long double XX=s/(1.0*SIZ); out(XX,k-1); }
其实第二个暴力给我们了一种接近标算的思路。
我们只要快速求出比M大的有几种。
那么我们考虑DP：
绝对值不好搞，那么我们按大小从小到大依次插入。
那么插入一个数有很多种情况。
1.插入以后它两边都没有数。
2.插入以后它两边都有数。
3.插入以后它的一边有数。
4.插入在边界上，且它旁边没有数。
5.插入在边界上，且它旁边有数。
这55种情况对应55个不同的转移，于是我们可以设一个状态来表示这些转移。
设f[i][j][k][l] 表示插入i个数，当前序列波动值为j，序列现在被分为k个连续的段，序列边界的状态为l，l为0表示边界没有数，为1表示边界有一个数，为2表示边界有两个数。
那么我们可以分几种情况转移，就好了。
__float128可以替代高精度。
#include<bits/stdc++.h> #define M 4500 using namespace std; int n,m,k; namespace db{ double f[2][9001][101][3]; } namespace f128{ __float128 f[2][9001][101][3]; } template<class T> inline void pout(T ans,int k){ printf("%d.",(int)ans); while (k--) { ans=(ans-(int)ans)*10; if(!k) ans+=0.5; printf("%d",(int)ans); } } template<class T> void solve(T f[][9001][101][3]){ T A; f[1][M-2][1][0]=1;f[1][M-1][1][1]=2;f[0][M][1][2]=1; for (int i=2,cur=0,pre=1;i<=n;i++,cur=pre,pre^=1) { memset(f[cur],0,sizeof f[cur]); for (int j=2*M;~j;j--) for (int k=n-1;k;k--) for (int l=2;~l;l--) { if (!(A=f[pre][j][k][l])) continue; if (j+2*i<=2*M) f[cur][j+2*i][k-1][l]+=A*(k-1); if (j>=2*i) f[cur][j-2*i][k+1][l]+=A*(k+1-l); f[cur][j][k][l]+=A*(k*2-l); if (l<2) { if (j+i<=2*M) f[cur][j+i][k][l+1]+=(2-l)*A; if (j>=i) f[cur][j-i][k+1][l+1]+=A*(2-l); } } } T ans=0;for (int i=M+m;i<=2*M;i++) ans+=f[n&1][i][1][2]; for (int i=2;i<=n;i++) ans/=i; pout(ans,k); } int main () { scanf("%d %d %d",&n,&m,&k); if (k<=8) solve(db::f); else solve(f128::f); }