QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#369892#2430. Gem IslandInfinityNSAC ✓74ms35848kbC++201.5kb2024-03-28 19:07:192024-03-28 19:07:23

Judging History

你现在查看的是最新测评结果

  • [2024-03-28 19:07:23]
  • 评测
  • 测评结果:AC
  • 用时:74ms
  • 内存:35848kb
  • [2024-03-28 19:07:19]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
typedef long double ld;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=1000+10;

ld dp[maxn][maxn],nck[maxn][maxn];

ld get_nck(int n,int k){
    if(n<0 || k<0 || n<k)return 0;
    if(nck[n][k]!=-1)return nck[n][k];
    if(k==0)return 1;
    nck[n][k]=get_nck(n-1,k)+get_nck(n-1,k-1);
    return nck[n][k];
}

int n,d,r;

ld go(int n,int d){

    ///printf("%d %d SS\n",n,d);

    if(d<0)return 0;
    if(n==0)return 0;
    ld pom=get_nck(d+n-1,n-1);
    if(n<=r)return (n+d)*pom;
    if(dp[n][d]!=-1)return dp[n][d];

    ///printf("%d %d RACUNA\n",n,d);

    ld &a=dp[n][d];
    a=0;

    for(int g=0;g<=n;g++){
        a+=get_nck(n,g)*go(n-g,d-n+g);
    }

    a+=pom*r;

    ///cout<<n<<" "<<d<<" "<<a<<endl;
    return a;
}

int main(){

    ///freopen("test.txt","r",stdin);

    for(int i=0;i<maxn;i++)
    for(int j=0;j<maxn;j++){
        dp[i][j]=-1;
        nck[i][j]=-1;
    }

    scanf("%d %d %d",&n,&d,&r);

    cout<<fixed<<setprecision(10)<<go(n,d)/get_nck(d+n-1,n-1);


    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 35768kb

Test #2:

score: 0
Accepted
time: 4ms
memory: 35768kb

Test #3:

score: 0
Accepted
time: 4ms
memory: 35764kb

Test #4:

score: 0
Accepted
time: 4ms
memory: 35768kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 35744kb

Test #6:

score: 0
Accepted
time: 13ms
memory: 35620kb

Test #7:

score: 0
Accepted
time: 4ms
memory: 35764kb

Test #8:

score: 0
Accepted
time: 4ms
memory: 35732kb

Test #9:

score: 0
Accepted
time: 8ms
memory: 35744kb

Test #10:

score: 0
Accepted
time: 3ms
memory: 35788kb

Test #11:

score: 0
Accepted
time: 4ms
memory: 35724kb

Test #12:

score: 0
Accepted
time: 4ms
memory: 35732kb

Test #13:

score: 0
Accepted
time: 4ms
memory: 35748kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 35664kb

Test #15:

score: 0
Accepted
time: 8ms
memory: 35724kb

Test #16:

score: 0
Accepted
time: 4ms
memory: 35748kb

Test #17:

score: 0
Accepted
time: 0ms
memory: 35664kb

Test #18:

score: 0
Accepted
time: 4ms
memory: 35764kb

Test #19:

score: 0
Accepted
time: 12ms
memory: 35788kb

Test #20:

score: 0
Accepted
time: 6ms
memory: 35776kb

Test #21:

score: 0
Accepted
time: 4ms
memory: 35788kb

Test #22:

score: 0
Accepted
time: 8ms
memory: 35752kb

Test #23:

score: 0
Accepted
time: 0ms
memory: 35764kb

Test #24:

score: 0
Accepted
time: 4ms
memory: 35728kb

Test #25:

score: 0
Accepted
time: 3ms
memory: 35768kb

Test #26:

score: 0
Accepted
time: 0ms
memory: 35736kb

Test #27:

score: 0
Accepted
time: 3ms
memory: 35760kb

Test #28:

score: 0
Accepted
time: 4ms
memory: 35740kb

Test #29:

score: 0
Accepted
time: 4ms
memory: 35768kb

Test #30:

score: 0
Accepted
time: 8ms
memory: 35656kb

Test #31:

score: 0
Accepted
time: 8ms
memory: 35744kb

Test #32:

score: 0
Accepted
time: 6ms
memory: 35748kb

Test #33:

score: 0
Accepted
time: 4ms
memory: 35752kb

Test #34:

score: 0
Accepted
time: 4ms
memory: 35732kb

Test #35:

score: 0
Accepted
time: 13ms
memory: 35768kb

Test #36:

score: 0
Accepted
time: 12ms
memory: 35720kb

Test #37:

score: 0
Accepted
time: 6ms
memory: 35764kb

Test #38:

score: 0
Accepted
time: 4ms
memory: 35752kb

Test #39:

score: 0
Accepted
time: 4ms
memory: 35660kb

Test #40:

score: 0
Accepted
time: 0ms
memory: 35772kb

Test #41:

score: 0
Accepted
time: 8ms
memory: 35660kb

Test #42:

score: 0
Accepted
time: 8ms
memory: 35740kb

Test #43:

score: 0
Accepted
time: 12ms
memory: 35696kb

Test #44:

score: 0
Accepted
time: 4ms
memory: 35792kb

Test #45:

score: 0
Accepted
time: 8ms
memory: 35760kb

Test #46:

score: 0
Accepted
time: 8ms
memory: 35748kb

Test #47:

score: 0
Accepted
time: 4ms
memory: 35768kb

Test #48:

score: 0
Accepted
time: 0ms
memory: 35748kb

Test #49:

score: 0
Accepted
time: 6ms
memory: 35808kb

Test #50:

score: 0
Accepted
time: 0ms
memory: 35788kb

Test #51:

score: 0
Accepted
time: 6ms
memory: 35812kb

Test #52:

score: 0
Accepted
time: 8ms
memory: 35764kb

Test #53:

score: 0
Accepted
time: 0ms
memory: 35784kb

Test #54:

score: 0
Accepted
time: 15ms
memory: 35712kb

Test #55:

score: 0
Accepted
time: 11ms
memory: 35824kb

Test #56:

score: 0
Accepted
time: 0ms
memory: 35740kb

Test #57:

score: 0
Accepted
time: 8ms
memory: 35772kb

Test #58:

score: 0
Accepted
time: 3ms
memory: 35732kb

Test #59:

score: 0
Accepted
time: 8ms
memory: 35760kb

Test #60:

score: 0
Accepted
time: 10ms
memory: 35752kb

Test #61:

score: 0
Accepted
time: 17ms
memory: 35764kb

Test #62:

score: 0
Accepted
time: 10ms
memory: 35736kb

Test #63:

score: 0
Accepted
time: 0ms
memory: 35768kb

Test #64:

score: 0
Accepted
time: 3ms
memory: 35764kb

Test #65:

score: 0
Accepted
time: 59ms
memory: 35848kb

Test #66:

score: 0
Accepted
time: 0ms
memory: 35808kb

Test #67:

score: 0
Accepted
time: 4ms
memory: 35788kb

Test #68:

score: 0
Accepted
time: 4ms
memory: 35808kb

Test #69:

score: 0
Accepted
time: 8ms
memory: 35792kb

Test #70:

score: 0
Accepted
time: 8ms
memory: 35788kb

Test #71:

score: 0
Accepted
time: 15ms
memory: 35840kb

Test #72:

score: 0
Accepted
time: 74ms
memory: 35828kb

Test #73:

score: 0
Accepted
time: 11ms
memory: 35780kb

Test #74:

score: 0
Accepted
time: 8ms
memory: 35760kb

Test #75:

score: 0
Accepted
time: 9ms
memory: 35780kb

Test #76:

score: 0
Accepted
time: 8ms
memory: 35784kb

Test #77:

score: 0
Accepted
time: 16ms
memory: 35696kb

Test #78:

score: 0
Accepted
time: 3ms
memory: 35800kb

Test #79:

score: 0
Accepted
time: 0ms
memory: 35780kb

Test #80:

score: 0
Accepted
time: 24ms
memory: 35808kb

Test #81:

score: 0
Accepted
time: 68ms
memory: 35796kb

Test #82:

score: 0
Accepted
time: 61ms
memory: 35820kb

Test #83:

score: 0
Accepted
time: 45ms
memory: 35836kb

Test #84:

score: 0
Accepted
time: 4ms
memory: 35816kb