首先一眼看出，n才5000，n2包能过的 既然是概率题大概是得dp了，用dp[i][j]表示第i时刻j位置上的概率然后一轮一轮去模拟就好了

我们还注意到题目提醒我们空间的问题，显然5000x5000的数组是开不下的，但是介于这一轮的概率之与上一轮有关，所以其实我们只要每轮都保存本轮的数据就好了，也就是实际上只需要2x5000，即O(n)的空间复杂度

最后注意！！！！控制输出位数，蚌埠住了我就是忘记了最后就拿了13分

#include<bits/stdc++.h>
using namespace std;
double solve(int n,int m,vector<int> p)
{
    vector<double> vp(n+1,0.0);
    vector<double> vn(n+1,0.0);
    vp[1]=1.0;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<=n;j++)
        vn[j]=0.0;
        for(int j=1;j<=n;j++)
        {
            if(vp[j]>0)
            {
                int next=j%n+1;
                vn[next]+=vp[j]*p[i]/100.0;
                next=(j+n-2)%n+1;
                vn[next]+=vp[j]*(100-p[i])/100.0;
            }
        }
        swap(vp,vn);
    }
    return vp[1];
}
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> v;
    for(int i=0;i<m;i++)
    {
        int t;
        cin>>t;
        v.push_back(t);
    }
    double res=solve(n,m,v);
    printf("%.9lf",res);
}

摇摆不定

每一次移动所在地块都可以由上一步的地块转移而来，可以采用动态规划。$dp[i][j]$ 代表第 $i$ 次移动后位于 $j + 1$ 号地块（编号从0开始便于取模）的概率，那么可以写出如下转移方程：

$$dp[i][j] = dp[i-1][(j-1)\%n] * p_{(j-1)\%n} / 100 + dp[i-1][(j+1)\%n] * (100 - p_{(j+1)\%n}) / 100 $$

最后 $dp[m][0]$ 即为答案。

但是根据题目所给空间限制，使用二维数组是会超过空间限制的。根据转移方程可以发现，第 $i$ 次移动只与第 $i-1$ 次移动有关，所以可以采用滚动数组，具体代码如下：

// p[i] = p[i] / 100
vector<double> dp(n, 0);
	
dp[0] = 1;
for(int i=0; i<m; i++)
{
	vector<double> ndp(n, 0);
	for(int j=0; j<n; j++)
	{
		ndp[(j+1)%n] += dp[j] * p[i];
		ndp[(j-1+n)%n] += dp[j] * (1 - p[i]);
	}
	dp = ndp;
}

最后 $dp[0]$ 即为答案，时间复杂度为 $O(nm)$，空间复杂度为 $O(n)$.