题意:
环形cell, robot初始在1号,顺逆时针走概率各半.每次走w,问x次后停在l和r之间的概率.
思路:
正着推,方程很显然. 需要注意空间优化为2行, 时间上减少mod的次数.
#include <cstdio> #include <cstring> using namespace std; const int MAXM = 1e6+5; const int MAXN = 205; double dp[2][MAXN]; int m,n,l,r,w; inline int mymod(int a, int mod)//[1,n] { return ((a-1)%mod + mod)%mod + 1; } int main() { while(scanf("%d %d %d %d",&n,&m,&l,&r) && (n+m+l+r)) { memset(dp[0],0,sizeof(dp[0])); dp[0][1] = 1; for(int i=1;i<=m;i++) { scanf("%d",&w); for(int j=1;j<=n;j++) { if(j-w>=1) { if(j+w<=n) dp[i&1][j] = 0.5*dp[(i&1)^1][j-w] + 0.5*dp[(i&1)^1][j+w]; else dp[i&1][j] = 0.5*dp[(i&1)^1][j-w] + 0.5*dp[(i&1)^1][mymod(j+w,n)]; } else { if(j+w<=n) dp[i&1][j] = 0.5*dp[(i&1)^1][mymod(j-w,n)] + 0.5*dp[(i&1)^1][j+w]; else dp[i&1][j] = 0.5*dp[(i&1)^1][mymod(j-w,n)] + 0.5*dp[(i&1)^1][mymod(j+w,n)]; } } } double ans = 0; for(int i=l;i<=r;i++) ans += dp[m&1][i]; printf("%.4lf\n",ans); } }