「AGC020F」 Arcs on a Circle

这个题非常 Amazing 啊。果然AtCoder全是智商题

首先你可以注意到数据范围真的是小得离谱，让你想要爆搜。

然后你发现不可做，那考虑状压。

首先你发现这是一个环很烦，所以我们随便找一个端点断环为链。

问题转换为求能覆盖整个圆的不同的覆盖方式。

但是显然这样的方案有无数种，我们需要考虑优化。

注意到两段圆弧是否相交，仅与它们的起始位置的整数部分的值和小数部分有关。更进一步地，他们小数部分的相对大小决定了其是否相交。

若有 \(p_i\le p_j\)，则两圆弧相交 \(\iff p_i+l_i\ge p_j\)。

拆分为整数和小数部分，有 \([p_i]+\{p_i\}+l_i\ge [p_j]+\{p_j\}\)。

若 \([p_i]+l_i\neq [p_j]\)，则小数部分无影响。

若 \([p_i]+l_i= [p_j]\)，则 \([p_i]+\{p_i\}+l_i\ge [p_j]+\{p_j\}\iff \{p_i\}\ge \{p_j\}\)。

不妨设相对位置互不相同。

于是我们可以考虑枚举所有圆弧小数部分的相对位置，然后状压DP即可。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

int s;

int a[10],tot;

long long ans;

int n,c;

int f[50][500];

int solve(){

	memset(f,0,sizeof f); f[0][a[n]*(n+1)]=1;

	for(int i=1;i<(n+1)*c;++i){

		if(i%(n+1)){

			int t=i%(n+1)-1,len=min(i+(n+1)*a[t],(n+1)*c);

			for(int j=0;j<=s;++j){

				if((j&(1<<t))==0){

					for(int k=i;k<=(n+1)*c;++k)

						f[j|(1<<t)][max(k,len)]+=f[j][k];

				}

			}

		}

	}

	return f[s][(n+1)*c];

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	cin>>n>>c;

	s=(1<<(n-1))-1;--n;

	for(int i=0;i<=n;++i) cin>>a[i];

	sort(a,a+n+1);

	do{

		ans+=solve();

		++tot;

	}while(next_permutation(a,a+n));

	cout<<setprecision(14)<<fixed<<(long double)ans/tot/pow(c,n)<<'\n';

	return 0;

}

巴特西

「AGC020F」 Arcs on a Circle

「AGC020F」 Arcs on a Circle

最新文章

热门文章