题目链接
题解
一道画风正常的……期望DP？
首先考虑如何以最小步数熄灭所有灯：贪心地从大到小枚举灯，如果它亮着则修改它。可以求出总的最小步数，设为\(cnt\)。
然后开始期望DP。设\(dp[i]\)为当前最小步数是\(i\)，总最小步数是\(i\)，要达到最小步数是\(i - 1\)的状态，期望要走多少步。则有\(\frac{i}{n}\)的几率恰好走了该走的一步，而有\(\frac{n - i}{n}\)的几率走错了（回到了\(dp[i + 1]\)表示的状态）。
则：\[dp[i] = \frac{i}{n} + \frac{n - i}{n}(1 + dp[i + 1] + dp[i])\]
就可以推出来了。
答案就是：\((\sum_{i = k + 1}^{cnt} dp[i] + min(cnt, k)) * n!\)
#include#include #include #include #include #include #define space putchar(' ')#define enter putchar('\n')using namespace std;typedef long long ll;template void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x;}template void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10);}const int N = 100005, P = 100003;int n, m, a[N], cnt;ll dp[N], ans;ll qpow(ll a, ll x){ ll ret = 1; while(x){ if(x & 1) ret = ret * a % P; a = a * a % P; x >>= 1; } return ret;}int main(){ read(n), read(m); for(int i = 1; i <= n; i++) read(a[i]); for(int i = n; i; i--) if(a[i]){ cnt++; for(int j = 1; j * j <= i; j++) if(i % j == 0){ a[j] ^= 1; if(j * j < i) a[i / j] ^= 1; } } for(int i = n; i; i--) dp[i] = 1 + (n - i) * qpow(i, P - 2) % P * (1 + dp[i + 1]) % P; for(int i = cnt; i > m; i--) ans = (ans + dp[i]) % P; ans = (ans + min(cnt, m)) % P; for(int i = 2; i <= n; i++) ans = ans * i % P; write(ans), enter; return 0;}