题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4576
题意：给出1~n的环，m个操作，每次能顺时针或逆时针走w步，询问最后在l~r这段区间内概率。
(1<=n<=200) ,(0<=m<=1,000,000),(1<=l<=r<=n).
分析：每次从某一个数字到达另外数字的概率为0.5，按概率dp求出到达每个数字的概率，然后枚举从l到r的概率相加即可。
dp[i][j]表示第i次操作落在数字j上的概率，但是不能直接开1000000*200的数组来保存中间结果，这肯定是会爆掉的。
因为每次只需要取上一次的数据，所以可以用滚动数组，开dp[2][200]就行了
注意：w可能比n大，所以要先w%n
这一题卡时限卡的非常紧，代码稍微写挫一点就会超时了。
代码如下：
#include<stdio.h>
#include<string.h>
double dp[][];
int main()
{
int n,m,l,r,i,t,k,w;
while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF)
{
if(n==&&m==&&l==&&r==)
break;
memset(dp,,sizeof(dp));
dp[][]=;
t=;
while(m--)
{
scanf("%d",&w);
w%=n;
k=t^;
for(i=;i<n;i++)
dp[k][i]=;
for(i=;i<n;i++)
{
if(!dp[t][i]) //时限卡的很紧，加这一句来优化，减少运算次数
continue;
dp[k][(i+w)%n]+=0.5*dp[t][i];
dp[k][(i-w+n)%n]+=0.5*dp[t][i];
}
t=k;
}
double ans=;
for(i=l;i<=r;i++)
ans+=dp[t][i-];
printf("%.4lf\n",ans);
}
return ;
}