题意：1-n的环，现在m次操作，每次顺时针或逆时针走w步，顺逆概率相同，问最后走完落在[l,r]内的概率是多少。
思路：dp，由于m很大，要滚动数组优化，dp[i][j]代表i步走到j这个位置的概率，那么只可能由i - 1步顺时针或逆时针到达，状态转移挺好想的。
主要是，这题卡时间也是卡得厉害，有点坑。
代码：
#include#include const int N = 205; int n, m, l, r, w, i, j, pre, now; double dp[2][N]; int main() { while (~scanf(%d%d%d%d, &n, &m, &l, &r) && n || m || l || r) { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (i = 1; i <= m; i++) { scanf(%d, &w); now = i&1; pre = !now; for (j = 0; j < n; j++) { if (dp[pre][j] == 0) continue;//不加超时 dp[now][(j + w) % n] += 0.5 * dp[pre][j]; dp[now][(j - w + n) % n] += 0.5 * dp[pre][j]; dp[pre][j] = 0; } } double ans = 0; for (i = l - 1; i < r; i++) ans += dp[m&1][i]; printf(%.4lf , ans); } return 0; }