HDU 4576

http://acm.hdu.edu.cn/showproblem.php?pid=4576

题意：给一个1-n的环，m次操作，每次操作顺时针或逆时针走w步，求最后落在[l,r]区间的概率

dp[i][j]表示第i步走到点j的概率，很裸的概率dp，i太大，需要滚动数组

时限4s，我的代码3984ms过的，有点悬

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

double dp[2][205];

int main() {
    int n, m, l, r;
    while(~scanf("%d %d %d %d", &n, &m, &l, &r)) {
        if(!n && !m && !l && !r) break;
        memset(dp, 0, sizeof(dp) );
        dp[0][0] = 1.0;
        int f = 0;
        while(m--) {
            int w;
            scanf("%d", &w);
            for(int i = 0; i < n; i++)
                dp[f ^ 1][i] = 0.0;
            for(int i = 0; i < n; i++) {
                dp[f ^ 1][(i + w) % n] += 0.5 * dp[f][i];
                dp[f ^ 1][(i - w + n) % n] += 0.5 * dp[f][i];
            }
            f ^= 1;
        }
        double ans = 0.0;
        for(int i = l; i <= r; i++)
            ans += dp[f][i-1];
        printf("%.4lf
", ans);
    }
    return 0;
}