题意：1-n围成1圈，从1出发，第i次走a[i]步，问走m次后出现在[L,R]的概率L<=R。
思路：明显的DP，把编号变成0~n-1，令dp[i][j]表示走完i步之前停在了j上，则有dp[i][j] * 0.5 -> dp[i+1][(j+a[i])%n] 和 dp[i+1][(j-a[i]+n*a[i])%n]。由于取模运算的大量存在，直接算会TLE，需要预处理取模的结果。时间复杂度O(nm)。
代码1：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <vector>using namespace std;typedef long long LL;#define mem0(a) memset(a, 0, sizeof(a))double dp[2][234];int mod1[234][234], mod2[234][234];int a[1234567];int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int n, m, l, r; while (cin >> n >> m >> l >> r, n) { for (int i = 0; i < m; i ++) scanf("%d", a + i); mem0(dp); dp[0][0] = 1; for (int i = 0; i < 201; i ++) { for (int j = 0; j < 201; j ++) { mod1[i][j] = (i + j) % n; mod2[i][j] = (i - j + n * j) % n; } } int cur = 1; for (int i = 0; i < m; i ++) { for (int j = 0; j < n; j ++) { dp[cur][mod1[j][a[i]]] += dp[cur ^ 1][j] * 0.5; dp[cur][mod2[j][a[i]]] += dp[cur ^ 1][j] * 0.5; } cur ^= 1; mem0(dp[cur]); } double ans = 0; for (int i = l - 1; i < r; i ++) { ans += dp[cur ^ 1][i]; } printf("%.4f
", ans); } return 0;} |
另一个思路（没A，应该是精度问题）:m次走的顺序是不会影响最终的结果的，所以考虑把相同的步数和并，由于步数范围在1-100，所以把m次走的过程分为了最多100个阶段，如果我们预处理每个阶段从0到任意点的概率（最多n个） ，那么就可以在O(1)的时间完成点到点的转移。时间复杂度变成O(m + k * n * n).
代码2：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <vector>using namespace std;typedef long long LL;#define mem0(a) memset(a, 0, sizeof(a))int cnt[123];double p[123][234], dp[123][234];int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int n, m, l, r; while (cin >> n >> m >> l >> r, n) { mem0(cnt); mem0(dp); mem0(p); for (int i = 0; i < m; i ++) { int x; scanf("%d", &x); cnt[x] ++; } for (int x = 1; x <= 100; x ++) { int tot = cnt[x]; if (tot == 0) continue; double buf = 1.0; for (int i = 0; i < tot; i ++) buf /= 2; for (int i = 0; i <= tot; i ++) { p[x][((LL)x * (tot - 2 * i) + (LL)n * tot * x) % n] += buf; buf *= ((double)tot - i) / (i + 1); } } mem0(dp); dp[0][0] = 1; int cur = 0; for (int x = 1; x <= 100; x ++) { if (cnt[x] == 0) continue; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[cur + 1][(i + j) % n] += p[x][j] * dp[cur][i]; } } cur ++; } double ans = 0; for (int i = l - 1; i < r; i ++) ans += dp[cur][i]; printf("%.4f
", ans); } return 0;} |