1 条题解
-
0
C++ :
#include <bits/stdc++.h> #define N 110 #define MAX 4500 using namespace std; typedef long long ll; int i,j,k,n,m,x,y,t,q,la,no; namespace dob {typedef double db;db f[2][9005][101][3];} namespace fl {typedef __float128 db;db f[2][9005][101][3];} template <class T> inline void print2(T x,int k){ for (i=2;i<=n;i++)x=x/(T)i; ll a=x;x-=a;int s[100],l,j=0;s[0]=0; while (a)s[++s[0]]=a%10,a/=10;if (!s[0])s[++s[0]]=0;l=s[0]; for (i=1;i<=k+1;i++){x*=10;a=(int)x;x-=a;s[++s[0]]=a;} if (s[s[0]]>=5)j=1;int p=s[0]; while (j&&p){s[p-1]++;j=s[p-1]/10;s[p-1]%=10;p--;} if (j){for (i=s[0];i>1;i--)s[i]=s[i-1];s[1]=1;} putchar('0'+s[1]);if (k)putchar('.');for (i=2;i<=k+1;i++)putchar(s[i]+'0'); return; } template <class T> inline void solve(T f[][9005][101][3]){ f[0][MAX-2*1][1][0]=1;f[0][MAX-1][1][1]=2;f[0][MAX][1][2]=1;no=0;la=1; for (int i=2;i<=n;i++){ no=1-no,la=1-la; memset(f[no],0,sizeof f[no]); for (int j=0;j<=MAX*2;j++) for (int k=1;k<=n-1;k++){ if (f[la][j][k][0]){ if (j>=2*i)f[no][j-2*i][k+1][0]+=f[la][j][k][0]*(k+1); if (j+2*i<=MAX*2)f[no][j+2*i][k-1][0]+=f[la][j][k][0]*(k-1); f[no][j][k][0]+=f[la][j][k][0]*k*2; if (j+i<=MAX*2)f[no][j+i][k][1]+=f[la][j][k][0]*2; if (j>=i)f[no][j-i][k+1][1]+=f[la][j][k][0]*2; } if (f[la][j][k][1]){ if (j>=2*i)f[no][j-2*i][k+1][1]+=f[la][j][k][1]*k; if (j+2*i<=MAX*2)f[no][j+2*i][k-1][1]+=f[la][j][k][1]*(k-1); f[no][j][k][1]+=f[la][j][k][1]*(2*k-1); if (j+i<=MAX*2)f[no][j+i][k][2]+=f[la][j][k][1]; if (j>=i)f[no][j-i][k+1][2]+=f[la][j][k][1]; } if (f[la][j][k][2]){ if (j+i*2<=MAX*2)f[no][j+i*2][k-1][2]+=f[la][j][k][2]*(k-1); if (j>=2*i)f[no][j-i*2][k+1][2]+=f[la][j][k][2]*(k-1); f[no][j][k][2]+=2*f[la][j][k][2]*(k-1); } } } T ans=0; for (int i=m+MAX;i<=MAX*2;i++)ans+=(T)f[no][i][1][2]; print2(ans,q); } int main(){ scanf("%d%d%d",&n,&m,&q);if (q<=8)solve(dob::f);else solve(fl::f); return 0; }
- 1
信息
- ID
- 978
- 时间
- 6000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者