学步园

题意：在一个圈上，起点是1，有m次移动，每次顺时针移动wi格或者逆时针移动wi格，顺时针和逆时针的概率都是1/2。问最后停留在l到r之间的概率

思路：显然的递推式子：p[i][j]=0.5*p[i-1]([j+w)%n]+0.5*p[i-1][(j-w+n)%n];。本人用了输入优化。

虽然很暴力，但还是勉强ac了。（网上某些题解用G++能过，C++不能过），然后据说还有矩阵乘法的方法可以更快。

还有，特别奇怪的是，如果把p[now][j]=0.5*p[pre][(j-w+n)%n]+0.5*p[pre][(j+w)%n]换成p[now][j]=0.5*(p[pre][(j-w+n)%n]+p[pre][(j+w)%n])就会TLE，求大神解答。。。

#include<cstdio>
#include<cstring>
#include<cctype>
#define MAXN 205
float p[2][MAXN];
inline int readint()
{
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    int x=0;
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main()
{
    int n,m,l,r;
    while(~scanf("%d%d%d%d",&n,&m,&l,&r))
    {
        if(!n && !m && !l && !r) break;
        int now=0,w,pre=1;
        memset(p[0],0,sizeof(p[0]));
        p[0][0]=1.0;
        while(m--)
        {
            w=readint();
            now^=1,pre^=1;
            for(int j=0;j<n;++j) p[now][j]=0.5*p[pre][(j-w+n)%n]+0.5*p[pre][(j+w)%n];
        }
        double ans=0.0;
        for(int i=l-1;i<r;++i) ans+=p[now][i];
        printf("%.4f\n",ans);
    }
    return 0;
}