hdu4576

题目

一个圆盘，有n个编号（1,2,3……n），从1出发，每次能逆时针或顺时针走w步，问经过m次后，最终停留在区间[l，r]的概率。

解析

首先，取模运算是一定要把1到n换成0到n-1；其次，利用temp来进行奇偶变换。

引用自博客：

https://www.cnblogs.com/kevinACMer/p/3723531.html

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define maxn 1000005
int n, m, l, r;
double dp[205][2];
int w[maxn];
int main(){
    while(scanf("%d%d%d%d", &n, &m, &l, &r) && (n || m || l || r)){
    	for(int i = 0; i < m; ++i) scanf("%d", &w[i]);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int cur = 0;
        for(int j = 0; j < m; ++j){
        	int t = w[j] % n;
            cur ^= 1;
            for(int i = 0; i < n; ++i)
            	dp[i][cur] = 0.5 * dp[(i + t) % n][cur ^ 1] + 0.5 * dp[(i - t) % n][cur ^ 1];
        }
        double ans = 0;
        for(int i = l - 1; i < r; ++i) ans += dp[i][cur];
        printf("%.4lf\n", ans);
    }
    return 0;
}