题目大意:

一个人在n长的路径上走到底再往回,走i步停下来的概率为Pi , 求从起点开始到自己所希望的终点所走步数的数学期望

因为每个位置都跟后m个位置的数学期望有关

E[i] = sigma((E[i+j]+j)*P[j])

我们需要将模型转化一下,本来路径为012345这样,因为来回走,我们多定义n-2个点就是 0123454321然后利用取模就可以不断找到下一组相关的m个点

列出多元方程组,利用高斯消元解决问题

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int N = ;
#define eps 1e-8 double a[N][N] , x[N] , p[N] , sum;
int n,m,st,en,dire;
int id[N] , cnt;//cnt记录需要求解的未知数个数 queue<int> q;
bool bfs()
{
memset(id , - , sizeof(id));
cnt = ;
id[st] = cnt++;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i= ; i<=m ; i++){
int v = (u+i)%n;
if(fabs(p[i])<eps || id[v]>=) continue;
id[v] = cnt++;
q.push(v);
}
}
return id[en]>= || id[n-en]>=; //终点有两个
}
//建立多元方程组
void build()
{
memset(a , , sizeof(a));
for(int i= ; i<n ; i++){
if(id[i] < ) continue;
int u=id[i];
a[u][u] = ;
if(u == id[en] || u == id[n-en]) {a[u][cnt]=;continue;}
for(int j= ; j<=m ; j++){
int v = (i+j)%n;
if(id[v]<) continue;
v = id[v];
a[u][v] -= p[j];
a[u][cnt] += p[j]*j;
}
}
/* for(int i=0 ; i<n ; i++)
{
for(int j=0 ; j<=n ; j++)
cout<<a[i][j]<<" ";
cout<<endl;
}*/
} int gauss(int n)
{
int i,j,k;
for(i=,j= ; i<n&&j<n ; j++){
for(k=i ; k<n ; k++)
if(fabs(a[k][j])>=eps) break;
if(k<n){
if(i!=k){
for(int r=j ; r<=n ; r++)
swap(a[i][r],a[k][r]);
}
double tt=1.0/a[i][j];
for(int r=j ; r<=n ; r++)
a[i][r]*=tt;
for(int r= ; r<n ; r++) //这从 0~n ,整个2重循环相当于消去和回代同时操作
if(r!=i){
for(int t=n ; t>=j ; t--) //一定是递减序
a[r][t] -= a[r][j]*a[i][t];
}
i++;
}
}
//检查是否还有未满足的方程式
for(int r=i ; r<n ; r++)
if(fabs(a[r][n])>=eps)
return ;
return ;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in" , "r" , stdin);
#endif // ONLINE_JUDGE
int T;
scanf("%d" , &T);
while(T--)
{
scanf("%d%d%d%d%d" , &n , &m , &en , &st , &dire);
n = *n-;
sum = ;
for(int i= ; i<=m ; i++){
int v;
scanf("%d" , &v);
p[i] = v*1.0/100.0;
sum += p[i]*i;
}
if(st == en){
puts("0.00");
continue;
}
if(dire>) st = n-st;
if(!bfs()){
puts("Impossible !");
continue;
}
build();
if(!gauss(cnt)) {
puts("Impossible !");
continue;
}
printf("%.2f\n" , a[][cnt]); }
return ;
}

最新文章

  1. 关于 bind 你可能需要了解的知识点以及使用场景
  2. 音频文件解析(一):WAV格式文件头部解析
  3. css3多列显示
  4. (笔记)VC6插件安装--Unable to register this add-in because its DllRegisterServer returns an error
  5. Jquery_异步上传文件多种方式归纳
  6. 在SSH框架中增加SiteMesh的支持
  7. IOS 取值控件(UIPicker)的使用方法
  8. wordpress安装插件--su
  9. (15)IO流之File
  10. iOS 正则表达式使用(转)
  11. OPPO realme 2在哪里打开Usb调试模式的简单步骤
  12. Java异常处理:给程序罩一层保险
  13. 《剑指offer》第一个只出现一次的字符
  14. jquery瀑布流排列样式代码
  15. 【转载】 PhpStudy修改Apache的端口号
  16. [20190227]简单探究tab$的bojb#字段.txt
  17. SpringBoot整合ssm
  18. 绑定本地的Session
  19. WARNING: Configuration &#39;compile&#39; is obsolete and has been replaced with &#39;implementation&#39; and &#39;api&#39;.
  20. Mysql 5.6 慢日志配制

热门文章

  1. jQuery选择器之子元素选择器
  2. 伟景行 citymaker 从入门到精通(3)——点击地图获取坐标,点击模型获取模型信息和属性信息
  3. Android手机屏幕投射到电脑神器Vysor
  4. 第3章 接口与API设计 52条笔记
  5. IDEA一些设置
  6. codevs 1979 第K个数
  7. Netbeans调试教程
  8. Devops 技术图谱
  9. 如何改android device monitor文件的权限
  10. 【转】《windows核心编程》读书笔记