题解:客星璀璨之夜
2021/8/2 6:35:59
本文主要是介绍题解:客星璀璨之夜,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
基本思路:
一道不错的概率与期望题。
考虑每段距离对答案的贡献。
每段距离以他右边的行星编号为编号,编号为\(2~2n+1\)。
可以发现,当两颗行星湮灭后,就变成了\(n-1\)的情况所以这实际上是可以递推的。
记\(f[i][j]\)表示情况为\(2i+1\)时第\(j\)条距离产生贡献的概率。
一条距离产生贡献,当且仅当有球经过。
可以是一开始的时候他左右的球经过他。
也可以是一些球湮灭后,其他球相互湮灭时经过他,这些球不一定一开始时在他两端。
接下来考虑转移方程:
枚举是那些球移动导致\(i\)向\(i-1\)变化,然后由\(i-1\)到推至\(i\)。
记\(j\)为边的编号
1.移动的球的编号是小于j-1的:
\[f[i][j]=(f[i][j]+f[i-1][j-2]*inv[i]); \]2.移动的球是j-1:
\[f[i][j]=(f[i][j]+f[i-1][j-2]*inv[i<<1]+(inv[2]+inv[2]*f[i-1][j-1])*inv[i]); \]3.移动的球是j
\[f[i][j]=(f[i][j]+(inv[2]+inv[2]*f[i-1][j-1])*inv[i]+inv[i<<1]*f[i-1][j]); \]4.移动的球比j大
\[f[i][j]=(f[i][j]+f[i-1][j]*inv[i]); \]
考虑球湮灭后当前距离会到\(i-1\)情况的那一段距离中贡献,从那个编号的边转移来。
\(j-1\)与\(j\)的情况,由于移动的球在移动时有50%的概率经过这段距离,所以除了上面正常的累加外,还要累加一个50%。
在取模意义下,所有除法写为乘逆元的形式。
代码
#include<bits/stdc++.h> using namespace std; namespace STD { #define rr register #define inf INT_MAX typedef long long ll; const int N=3004; const ll mod=998244353; int n; ll x[N<<1]; ll f[N][N<<1]; ll inv[N<<1]; ll read() { rr ll x_read=0,y_read=1; rr char c_read=getchar(); while(c_read<'0'||c_read>'9') { if(c_read=='-') y_read=-1; c_read=getchar(); } while(c_read<='9'&&c_read>='0') { x_read=(x_read<<3)+(x_read<<1)+(c_read^48); c_read=getchar(); } return x_read*y_read; } void pre() { inv[0]=inv[1]=1; for(rr int i=2;i<=(N<<1);i++) inv[i]=((mod-mod/i)*inv[mod%i])%mod; } }; using namespace STD; int main() { pre(); n=read(); for(rr int i=1;i<=(n<<1)+1;i++) x[i]=read(); for(rr int i=2;i<=3;i++) f[1][i]=inv[2]; for(rr int i=2;i<=n;i++)//枚举第几层 { for(rr int j=2;j<=(i<<1)+1;j++)//枚举哪条边 { ll x1,x2=((i<<1)+1-j)>>1; x1=i-1-x2; f[i][j]=(f[i][j]+x1*f[i-1][j-2]%mod*inv[i]%mod)%mod; if(j&1) f[i][j]=((f[i][j]+f[i-1][j-2]*inv[i<<1]%mod)%mod+(inv[2]+inv[2]*f[i-1][j-1]%mod)%mod*inv[i]%mod)%mod; else f[i][j]=((f[i][j]+(inv[2]+inv[2]*f[i-1][j-1]%mod)%mod*inv[i]%mod)%mod+inv[i<<1]*f[i-1][j])%mod; f[i][j]=(f[i][j]+x2*f[i-1][j]%mod*inv[i]%mod)%mod; } } ll ans=0; for(rr int i=2;i<=((n<<1)+1);i++) ans=(ans+(x[i]-x[i-1])*f[n][i]%mod)%mod; printf("%lld\n",ans); }
后言:
代码中提供了一个优化,因为原思路直接打的话是\(O(n^{3})\),会\(T\),可以计算一下累加的次数,将循环变为一个乘法,就能到\(O(n^{2})\)。
2021-07-31 06:29:11 星期六 现役
这篇关于题解:客星璀璨之夜的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)