• 好题啊！以后就按照这样的策略水分！等等似乎如果奶牛不那么蠢的话早就水满分了。
• 就是最后发现数据点多的时候得分根本上不去十分的尬。
• 为啥要用矩阵乘法啊，普及组蒟蒻表示不解。
• 普及组蒟蒻只会用 $\text{C++}$ 特性，但复杂度好像是 $O(n)$ 的呢。
• 普及组蒟蒻不知道库函数复杂度很合理吧，作者猜测由于浮点数的特性，计算方法可能与数值大小关系不大。

题目

• 你有 $T$ 道判断题，你只会做第一道，所以你打算其它的你瞎蒙。
• 你最多可以交 $K$ 次，每次你都可以得到成绩，但是你的自主权只有：是否把这次作为最终成绩，或者放弃这次结果重新提交一份？你由于智商，每次都会交随机数。
• 如果你充分利用你的自主权，使用最优策略，你期望可以拿到多少分？
• $2\le T\le 10^3,1\le K\le 10^9$。

分析

• 首先，你发现对于一个固定的局面：还有 $K$ 个测试点，你得到了分数 $S$，你交还是不交是固定的，那么显然有一个 $f(K)$，大于等于它你就不需要再交，否则你还是再交一次，利用组合数，我们可以 $O(n^2)$ 得到它的概率分布，枚举最优转移点，我们就得到了 $O(nk)$ 的暴力，代码。
• 然后你发现你实际上是在求一个凸壳的最值，由于转移点单调，我们可以用类似旋转卡壳的方法做到 $O(k)$，代码，或者你发现 $K-1$ 的期望就是 $f(K)$ 也可以，代码。
• 然后你发现转移点相同的迭代过程的嵌套，展开出来是这样的：比如把 $ax+b\to x$ 赋值 $n$ 次，展开是一个等比数列求和，为 $a^nx+\frac{a^n-1}{a-1}\cdot b$ 这可以用库函数直接算（需要特判 $a=1,b=0$）。
• 显然答案满足单调性，所以我们二分就得到了 $O(n^2+n\log k)$ 的方法，代码。
• $O(n^2)$ 显然可以优化，为了考虑精度，这里对阶乘取 $\ln$，可以防止掉精度，复杂度 $O(n\log k)$，代码，其实这份代码精度最高。
• 或许我们有更好的，不用二分的方法，那就是对函数进行分析，我们之前的做法本质上就是找到每个 $f(K)$ 的取值在 $K$ 上形成的区间，那么反正我们有强大的库函数，直接找不就行了？
• 如果函数嵌套之后没有增加，就直接跳，否则直接求出它的作用区间就好了，复杂度 $O(n)$，代码。

```cpp
#include<bits/stdc++.h>
const int N=1100;
using namespace std;
int n,k;
double fr[N],C[N],t[N],b[N];
double fun(double x,int i,int c)
{
	return x*pow(t[i],c)+(pow(t[i],c)-1)/(t[i]-1)*b[i];
}
int main()
{
	scanf("%d%d",&n,&k);--n,--k;
	t[n+1]=1,b[n+1]=0,fr[0]=0;
	for(int i=1;i<=n;++i)fr[i]=fr[i-1]+log(i);
	const double x=n*log(2);
	for(int i=n;i>=0;--i)
		C[i]=exp(fr[n]-fr[i]-fr[n-i]-x),
		t[i]=t[i+1]-C[i],b[i]=b[i+1]+C[i]*i;
	double res=b[0];
	for(int i=b[0],j=k;i<=n&&j>0;++i)
		if(res*t[i]+b[i]>res*t[i+1]+b[i+1])
		{
			double pos=(b[i]-b[i+1])/(t[i+1]-t[i]),qos=b[i]/(t[i]-1),qwq=(qos+pos)/(res+qos);
			int c;
			if(qwq>0)c=log(qwq)/log(t[i]);
			else c=j;
			c=min(c+1,j),res=fun(res,i,c),j-=c;
		}
	printf("%lf",res+1);
	return 0;
}