Submission #2826780

---

Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

using C = complex<R>;
const R pi = acos(-1.0L); 
// いざという時は複素数の掛け算を自分で定義する
void fft(vector<C> &a, bool inv) {
	const int n = a.size();
	const R sign = (inv ? -1.0 : 1.0);

	int rj = 0;
	rep(j, 1, n - 1) {
		for (int k = n >> 1; k > (rj ^= k); k >>= 1);
			if (j < rj) swap(a[j], a[rj]);
	}

	for (int m = 1; m < n; m <<= 1) {
		C wn = exp(C(0.0, sign * pi / m)), w = 1.0;
		rep(p, m) {
			for (int s = p; s < n; s += 2 * m) {
				C u = a[s], v = a[s + m] * w;
				a[s] = u + v, a[s + m] = u - v;
			}
			w *= wn;
		}
	}
	if (inv) rep(i, n) a[i] /= n;
}

const int all = 1 << 18;
int a[all],b[all];
vector<C> coef[19];

R E[all];

inline R effect(int pos){
	if(b[pos] < 0)
		return E[pos] - b[pos];
	else
		return E[pos + b[pos]];
}

int target;

bool solve(int l,int r,int idx){
	if(target - 1 <= l) return false;
	//cerr << l << " " << r << endl;
	const int m  = (l + r) / 2;
	if(r - l == 1){
		E[l] += 1.0;
		return true;
	}
	
	if(solve(m,r,idx-1)){
		const int len =  1 << idx;
		vector<C> ary(len, 0.0);

		rep(i,m,r){
			R cur = effect(i); 
			ary[r - 1 - i] = cur;
			//cerr << r - 1 - i << " " << ary[r - 1 - i] << " ";
		}
		

		fft(ary,0);
		rep(i,len) ary[i] *= coef[idx][i];
		fft(ary,1);

		rep(i,l,m){
			E[i] += real(ary[r - 1 - i]);
		}
	}

	//cerr << "Log: " <<  l << " " << r << " " << idx << endl;
	//rep(i,10) cerr << E[i] << endl;
	
	solve(l,m,idx-1);
	return true;
}



int main(void){
	int n,m;
	cin >> n >> m;
	target = m;

	rep(i,n){
		int aidx;
		cin >> aidx;
		a[aidx]++;
	}

	rep(i,19){
		const int len =  1 << i;
		coef[i] = vector<C>(len,0.0);
		const int num = min(len, m);
		rep(j,1,num) coef[i][j] = 1.0 * a[j] / n;
		fft(coef[i],0);
	}

	rep(i,m) cin >> b[i];

	rep(i,all) E[i] = 0.0;

	// int start = 0;
	// while((1 << start) < m) start++;
	solve(0,all,18);

	//rep(i,m) cerr << fixed << E[i] << endl;

	R ans = E[0];
	cout.precision(20);
	cout << fixed << ans << endl;

	return 0;
}

Submission Info

Judge Result