[noi Simulation Competition] scraping (dynamic planning)

Topic

　 Data range

about 100% The data of ,$1\le n\le 15,1\le m\le 100,1\le a_i\le 100,\sum a_i\ge m$, Don't worry about accuracy .

Answer key

and 「 General evaluation number 」 It's the same routine .

Consider the sequence of operations , Let's say there are $k$ Monsters were defeated , The order of death time from small to large is $t_1,t_2,...,t_k$ , So in $(t_i,t_{i+1}]$ Sequence elements between , Probability weights are $\frac{1}{n-i}$ . The contribution of a sequence of probability weights , Equal to the product of probability weight multiplied by the number of operation sequence schemes corresponding to the weight sequence .

In particular , We can consider defeated monsters and monsters that will not be defeated separately , When we determine the set of defeated monsters $S$ And the arrangement of defeated monsters in the operation sequence , That is, when the probability weight sequence is determined at the same time , What's left is the number of schemes that will not be defeated monsters put casually in a fixed position .

Make $g[i][S]$ Indicates that the monsters that will not be defeated are $S$ , The total blood loss is $i$ Number of alternatives , This can be transferred by backpack , Processing time complexity $O(2^n{m}^2)$ , constant <1.

Next, determine the probability weight sequence , Make $f[i][S]$ Indicates that it has been scraped $i$ , The defeated monsters are gathered as $S$ , Sum of weight products of all schemes . Let's fill in the operation sequence later , Confirm one by one $t_i$ And defeated monsters $j$, Put... Into the operation sequence when it is confirmed $a_j$ individual $j$ . Make $sum[S]={\sum }_{i\in S}{a}_i$, Transfer as follows ：

• The current location does not belong to $\{t\}$ ：$f[i+1][S]\leftarrow f[i][S]\cdot \frac{1}{n-|S|}$
• The current location belongs to $\{t\}$ ：$f[i+1][S\cup j]\leftarrow f[i][S]\cdot \left(\genfrac{}{}{0ex}{}{i-sum[S]}{a_j-1}\right)\cdot \frac{1}{n-|S|}$

Time complexity $O(2^{n}nm)$ .

The answer for ${\sum }_{S}f[m][S]\cdot g[m-sum[S]][\overline{S}]\cdot |S|$

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define MAXN 105
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int n,m,s,o,k;
int a[MAXN],id[1<<15|5],sm[1<<15|5],ct[1<<15|5];
DB g[MAXN][1<<15|5];
DB f[MAXN][1<<15|5];
DB C[MAXN][MAXN];
int main() {
    
	freopen("scraping.in","r",stdin);
	freopen("scraping.out","w",stdout);
	n = read(); m = read();
	for(int i = 1;i <= n;i ++) {
    
		a[i] = read();
	}
	C[0][0] = 1;
	for(int i = 1;i <= m;i ++) {
    
		C[i][0] = C[i][i] = 1;
		for(int j = 1;j < i;j ++) {
    
			C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
	}
	int tp = (1<<n)-1;
	for(int i = 1;i <= n;i ++) id[1<<(i-1)] = i;
	for(int i = 1;i <= tp;i ++) {
    
		sm[i] = sm[i^lowbit(i)] + a[id[lowbit(i)]];
		ct[i] = ct[i^lowbit(i)] + 1;
	}
	for(int i = 0;i <= tp;i ++) g[0][i] = 1;
	for(int i = 1;i <= m;i ++) {
    
		for(int j = 1;j <= tp;j ++) {
    
			g[i][j] = g[i][j^lowbit(j)];
			int d = id[lowbit(j)],jj = j^lowbit(j);
			for(int k = 1;k <= i && k < a[d];k ++) {
    
				g[i][j] += g[i-k][jj] * C[i][k];
			}
		}
	}
	f[0][0] = 1;
	for(int i = 0;i < m;i ++) {
    
		for(int j = 0;j < tp;j ++) {
    
			if(sm[j] > i) continue;
			f[i+1][j] += f[i][j]/ct[j^tp];
			for(int k = 1;k <= n;k ++) {
    
				if(!(j & (1<<(k-1)))) {
    
					if(sm[j]+a[k] <= i+1) f[i+1][j|(1<<(k-1))] += f[i][j]*C[i-sm[j]][a[k]-1]/ct[j^tp];
				}
			}
		}
	}
	DB as = 0;
	for(int i = 1;i <= tp;i ++) {
    
		if(sm[i] <= m) as += f[m][i] * g[m-sm[i]][i^tp] * ct[i];
	}
	as = floor(as*100000.0 + 0.5) * 1e-5;
	printf("%.5f\n",as);
	return 0;
}