题解 P3802 【小魔女帕琪】

· · 题解

表示做题的时候并不会楼下大佬的神奇算法（虽然式子看上去很简单）

题意相当于要求一个每种数字个数给定的数列中出现连续7个元素各不相同的次数的期望

那么我们考虑每7个连续的位置，这些位置产生贡献的概率是相同的

因此直接暴搜搞出第一段连续的位置(1-7)中产生贡献的概率，之后\times(\sum_{i=1}^{7}{a_i}-7+1)即可

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e9+7;
const int N=3000010;
const int M=90000;
il ll read(){
    RG ll data=0,w=1;RG char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
    return data*w;
}

il void file(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
}

int a[10],cnt[10],tot;
dd ans;

void dfs(int x,dd p){
    if(x==8){
        for(RG int i=1;i<=7;i++)
            if(!cnt[i])return;
        ans+=p;return;
    }
    for(RG int i=1;i<=7;i++)
        if(a[i]){
            a[i]--;cnt[i]++;
            dfs(x+1,p*(a[i]+1)/(tot-x+1));
            a[i]++;cnt[i]--;
        }
}

int main()
{
    for(RG int i=1;i<=7;i++)a[i]=read(),tot+=a[i];
    dfs(1,1);printf("%.3lf\n",ans*(tot-7+1));
    return 0;
}