一.
OSU!
题目背景
原 《产品排序》 参见P2577
题目描述
osu 是一款群众喜闻乐见的休闲软件。
我们可以把 osu 的规则简化与改编成以下的样子:
一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\)，失败对应 \(0\)，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(x\) 个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\)，具体见样例解释）
现在给出 \(n\)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。
输入格式
第一行有一个正整数 \(n\)，表示操作个数。接下去 \(n\) 行每行有一个 \([0,1]\) 之间的实数，表示每个操作的成功率。
输出格式
只有一个实数，表示答案。答案四舍五入后保留 \(1\) 位小数。
样例 #1
样例输入 #1
3
0.5
0.5
0.5
样例输出 #1
6.0
提示
【样例说明】
\(000\) 分数为 \(0\)，\(001\) 分数为 \(1\)，\(010\) 分数为 \(1\)，\(100\) 分数为 \(1\)，\(101\) 分数为 \(2\)，\(110\) 分数为 \(8\)，\(011\) 分数为 \(8\)，\(111\) 分数为 \(27\)，总和为 \(48\)，期望为 \(\dfrac{48}8 = 6.0\)。
\(n \leq 1 \times 10 ^ 5\)。
一.背景
《osu!》是一款Microsoft Windows平台上的同人音乐游戏。由Dean Herbert（Peppy）使用.NET Framework中的C#编写，后来升级为.NET 6.0并陆续在Mac OS、iOS、Android、Windows Phone等平台推出。游玩方式的设计参考了《押忍！战斗！应援团》、《太鼓达人》、《BeatmaniaIIDX》、《O2Jam》和《DJMax》，游戏共有osu!标准模式、osu!taiko、osu!catch以及osu!mania共四种玩法，深受各类音乐游戏玩家的喜爱。
二.前言
先用状压的思想做但是发现\(n\leq 1\times10^5\)
对于每个状态算出它的概率和求和然后加到一块容易写出一下代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void Write(int x){
if(x>9) Write(x/10);
putchar(x%10+'0');
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
Write(x);
putchar('\n');
}
}
using namespace Testify;
const int N=1e5+5;
int n;
double op[N];
inline double P(int s){
double Ecstasy(1);
int cnt(0);
for(register int i=1;i<=n;i++){
cnt++;
if(s&1){
Ecstasy*=op[cnt];
}
else{
Ecstasy*=(1.0-op[cnt]);
}
if(s){
s>>=1;
}
}
return Ecstasy;
}
inline double Sigma(int s){
int Ecstasy(0);
int cnt=0;
while(s){
while(s&1){
cnt++;
s>>=1;
}
Ecstasy+=(cnt*cnt*cnt);
cnt=0;
s>>=1;
}
return Ecstasy;
}
signed main(){
n=read();
for(register int i=1;i<=n;i++){
scanf("%lf",&op[i]);
}
double Tempestissimo(0);
for(register int s=1;s<(1<<n);s++){
double gai=P(s);
Tempestissimo+=(gai*Sigma(s));
}
printf("%.1lf",Tempestissimo);
return 0;
}
然后得了10分
因为\(n\)数据太大，肯定不能暴力枚举
三.思路
对于每个排列
$\ \ \ \ \ \ \ (x+1)^3 $
\(=(x+1)\times (x+1)\times (x+1)\)
\(=(x^2+2x+1)\times (x+1)\)
\(=x^3+x^2+2x^2+2x+x+1\)
\(=x^3+3x^2+3x+1\)
所以
\((x+1)^3\)比\(x^3\)多了\(3x^2+3x+1\)
即\(x^3[i]=x^3[i-1]+3\times x^2[i-1]+3\times x^1[i-1]+1\)
$\ \ \ \ \ \ \ (x+1)^2 $
\(=(x+1)\times (x+1)\)
\(=x^2+2\times x+1\)
所以
\((x+1)^2\)比\(x^2\)多了\(2\times x+1\)
即\(x^2[i]=x^2[i-1]+2\times x^1[i-1]+1\)
那么我们只需要维护\(x^2\)和\(x^1\)的期望 就能求出\((x+1)^3\)力
设\(dp[i]\)表示前\(i\)种情况の期望,即\(x^3[i]\)
\(x1[i]\)表示第\(i\)种情况的\(x\)の期望,即\(x^2[i]\)
\(x2[i]\)表示第\(i\)种情况的\(x^2\)の期望,即\(x^1[i]\)
那么我们可以得到式子
