一道入门概率dp:   http://acm.hdu.edu.cn/showproblem.php?pid=4576

分析:为了方便取模,把环的范围设置为0到n-1。使用滚动数组节省空间，因为可能多次操作的w相同所以第一维不可省略。第一维大小设置为2即可。这题学了一个用异或简化代码
转移方程:f[now^1][i]=0.5*f[now][(i+w)%n]+0.5*f[now][(i-w+n)%n];  (now为现在所在状态，now^1为要计算的状态)

代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 203;
double f[2][maxn];
int main()
{
    int n,l,r,m;
    while(~scanf("%d%d%d%d",&n,&m,&l,&r))
    {
        if(n==0&&m==0&&l==0&&r==0) break; 
        int now=0;
        f[0][0]=1;
        for(int i=1;i<n;i++) f[0][i]=0;
        while(m--)
        {
            int w;
            scanf("%d",&w);
            for(int i=0;i<n;i++) f[now^1][i]=0.5*f[now][(i+w+n)%n]+0.5*f[now][(i-w+n)%n];
            now^=1;
        }
        double ans=0.0;
        for(int i=l-1;i<r;i++) ans+=f[now][i];
        printf("%.4lf\n",ans);
    }
    return 0;
}