QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111039#6565. Game Show EliminationHe_RenAC ✓3004ms128868kbC++174.5kb2023-06-05 16:49:052023-06-05 16:49:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-05 16:49:08]
  • 评测
  • 测评结果:AC
  • 用时:3004ms
  • 内存:128868kb
  • [2023-06-05 16:49:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;
const int MAXN = 1000 + 5;
const int MAXD = 10 + 5;
const int ALL = (1<<10) + 5;
const ldb eps = 1e-12;

inline int sgn(ldb x){ return x<-eps? -1: x>eps? 1: 0;}

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)

using Poly = vector<ldb>;

Poly& operator += (Poly &A,const Poly &B)
{
	if(A.size() < B.size()) A.resize(B.size());
	for(int i=0; i<(int)B.size(); ++i)
		A[i] += B[i];
	return A;
}
Poly mul(Poly A,ldb k,ldb b)
{
	Poly res(A.size() + 1);
	for(int i=0; i<(int)A.size(); ++i)
	{
		res[i+1] += A[i] * k;
		res[i] += A[i] * b;
	}
	return res;
}

int n,d;

ldb getprob(vector<int> vec,int x)
{
	ldb res = 0;
	for(int k=0; k<d; ++k)
	{
		vector<Poly> f(2);
		f[0] = {(ldb)1 / d};
		for(int y: vec)
		{
			if(y == x) continue;
			if(y+d <= x+k) continue;
			
			if(y >= x+k+1)
			{
				f[1] = f[0];
				f[0] = {};
				continue;
			}
			
			vector<Poly> nf(2);
			nf[0] += mul(f[0], (ldb)1 / d, (ldb)-y / d);
			nf[1] += mul(f[1], (ldb)1 / d, (ldb)-y / d);
			nf[1] += mul(f[0], (ldb)-1 / d, (ldb)(y+d) / d);
			f = nf;
		}
		
		ldb l = 1, r = 1;
		for(int i=0; i<(int)f[1].size(); ++i)
		{
			if(!sgn(f[1][i])) continue;
			l *= x+k;
			r *= x+k+1;
			res += (r - l) * f[1][i] / (i+1);
		}
	}
	
//	printf("vec: ");
//	for(auto t: vec)
//		printf("%d ",t);
//	printf("\n");
//	printf("x = %d\n",x);
//	printf("prob = %lf\n",res);
	
	return res;
}

tuple<int,int,int> getnxt(int i,int mask,int fir,int j)
{
	vector<int> vec = {i + fir, i};
	for(int k=1; k<=2*d; ++k) if(k>d-1 || bdig(mask, k-1))
		vec.emplace_back(i - k);
	vec.erase(find(vec.begin(), vec.end(), j));
	
	int nxt = 0;
	for(int t: vec)
		if(vec[1]-d < t && t < vec[1])
			nxt |= bbit(vec[1] - t - 1);
	
	return make_tuple(vec[1], nxt, vec[0] - vec[1]);
}

int main(void)
{
	scanf("%d%d",&n,&d);
	
	int all = (1<<(d-1))-1;
	
	static vector< tuple<int,int,int,ldb,int> > trans[ALL][MAXD];
	
	for(int mask=0; mask<=all; ++mask)
		for(int fir=1; fir<=d; ++fir)
		{
			int i = 10 * d;
			
			vector<int> vec = {i + fir, i};
			for(int k=1; k<=2*d; ++k) if(k > d-1 || bdig(mask, k-1))
				vec.emplace_back(i - k);
			
			for(int t: vec)
			{
				ldb coef = getprob(vec, t);
				if(!sgn(coef)) continue;
				
				auto to = getnxt(i, mask, fir, t);
				get<0>(to) -= i;
				
				trans[mask][fir].emplace_back(tuple_cat(to, make_tuple(coef, t - i)));
			}
		}
	
	static ldb dp[MAXN][ALL][MAXD];
	static ldb ans[MAXN];
	
	dp[n-1][all][1] = 1;
	for(int i=n-1; i>=0; --i)
		for(int mask=all; mask>=0; --mask)
			for(int fir=d; fir>=1; --fir)
			{
				ldb cur = dp[i][mask][fir];
				if(sgn(cur) <= 0) continue;
				
//				printf("\n");
//				printf("dp[%d][%d][%d] = %lf\n",i,mask,fir,cur);
				
				int rem = 0;
				rem += n-i-1;
				rem += d-1 - (int)__builtin_popcount(mask);
				rem = n - rem;
				
//				printf("rem = %d\n",rem);
				
				if(i-2*d >= 1)
				{
					for(auto t: trans[mask][fir])
					{
						int ni = i + get<0>(t);
						int nmask = get<1>(t);
						int nfir = get<2>(t);
						ldb nxt = cur * get<3>(t);
						
						if(nfir > d)
						{
							ans[ni+nfir] += nxt;
							ans[ni+d] -= nxt;
							nfir = d;
						}
						
						int k = i + get<4>(t);
						ans[k] += nxt * rem;
						
						dp[ni][nmask][nfir] += nxt;
					}
					continue;
				}
				
				if(i == 0)
				{
					ans[fir] += cur;
					continue;
				}
				
				vector<int> vec = {i + fir, i};
				for(int k=1; k<=2*d; ++k) if(i - k >= 1 && (k > d-1 || bdig(mask, k-1)))
					vec.emplace_back(i - k);
				
//				printf("\n");
//				printf("vec: ");
//				for(auto t: vec)
//					printf("%d ",t);
//				printf("\n");
				
				for(int k: vec)
				{
					ldb coef = getprob(vec, k);
					if(!sgn(coef)) continue;
//					printf("del %d, prob = %lf\n",k,coef);
					
					auto t = getnxt(i, mask, fir, k);
					
					int ni = get<0>(t);
					int nmask = get<1>(t);
					int nfir = get<2>(t);
					ldb nxt = cur * coef;
					
					if(nfir > d)
					{
						ans[ni+nfir] += nxt;
						ans[ni+d] -= nxt;
						nfir = d;
					}
					
					ans[k] += nxt * rem;
					
//					printf("to %d %d %d\n",ni,nmask,nfir);
//					printf("ans[%d] += %lf * %d\n",k,nxt,rem);
					
					dp[ni][nmask][nfir] += nxt;
				}
			}
	
	for(int i=1; i<=n; ++i)
		printf("%.15lf\n",(double)ans[i]);
	return 0;
}

詳細信息

Test #1:

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

input:

3 2

output:

2.109375000000000
2.625000000000000
1.265625000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 3004ms
memory: 128868kb

input:

1000 10

output:

2.927293815167034
3.537316759339912
4.281182932480037
5.131221534154514
6.053933810161562
7.019189705439029
8.005703762736966
9.001292563577303
10.000166911078047
11.000001873758144
12.000002044190177
13.000002214010852
14.000002383330358
15.000002554401989
16.000002724417811
17.000002894599088
18.0...

result:

ok 1000 numbers

Test #3:

score: 0
Accepted
time: 308ms
memory: 16264kb

input:

300 8

output:

2.751263041338706
3.390073714740936
4.175006849914750
5.066021501039692
6.020146535973711
7.004557833455156
8.000572564004493
8.999999967308991
9.999999963676494
10.999999960047575
11.999999956413939
12.999999952781771
13.999999949152613
14.999999945518139
15.999999941884257
16.999999938252031
17.99...

result:

ok 300 numbers

Test #4:

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

input:

1000 3

output:

2.230256168087017
3.034765671091544
3.999999999971443
4.999999999964303
5.999999999957164
6.999999999950025
7.999999999942886
8.999999999935746
9.999999999928606
10.999999999921467
11.999999999914328
12.999999999907189
13.999999999900050
14.999999999892909
15.999999999885770
16.999999999878629
17.99...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 1905ms
memory: 8268kb

input:

7 10

output:

2.981586438371783
3.493604960118067
3.965342264912735
4.319677058587534
4.508724856222704
4.498880847650540
4.232183574136635

result:

ok 7 numbers

Test #6:

score: 0
Accepted
time: 987ms
memory: 69412kb

input:

993 9

output:

2.841121465169590
3.464359533207531
4.227324719562990
5.096943022722247
6.035282168519746
7.010574826762612
8.002388060805151
9.000303268069178
10.000000832941870
11.000000916222541
12.000000999686995
13.000001083112338
14.000001166545635
15.000001249709054
16.000001332936428
17.000001416200512
18.0...

result:

ok 993 numbers