题解 P3750 【[六省联考2017]分手是祝愿】

· · 题解

我这个小菜鸡来水题解，完全是因为没有看到和我一样解dp的人QAQ

50\% 的数据

对于 k=n 的数据，我们只需要求出，最少要操作多少次，能够关上所有的灯。

注意到 n 号灯只能用开关 n 控制，所以开关 n 是否要操作是固定的。此时，对于 n-1 号灯来说，前面的开关都无法调整，所以开关 n-1 是否要操作也唯一固定。对于 n-2,n-3,\dots,1 都是一样的。

调和级数 \mathcal O(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor)=\mathcal O(n\log n) ，所以复杂度有保障。

100\% 的数据

从上面的分析来看，最优操作方案是唯一的。所以，如果我们按了本就该按的开关，最优方案就可以少按一次；反之，最优方案就要多按一次开关。所以，转移只跟最优方案需要按开关的次数有关。

于是，我们可以设计出一个 dp ，用 f(x) 表示最优方案需要按 x 次按钮时，期望操作次数。很简单可以写出

f(x)=\frac{x}{n}\cdot f(x-1)+\frac{n-x}{n}\cdot f(x+1)+1 \Rightarrow\;(n-x)\cdot f(x+1)=n\cdot f(x)-x\cdot f(x-1)-n

这个式子只对 x\in(k,n] 有效，所以不能把 x=k 直接代入求值。但是我们可以解方程！

不妨设

f(x)=a_x\cdot f(k+1)+b_x

根据 dp 方程式，a_{x+1} 可以由 a_{x-1},a_x 推出，b 类似。边界也很好写，

\begin{cases}a_k=0\\b_k=f(k)\end{cases},\;\begin{cases}a_{k+1}=1\\b_{k+1}=0\end{cases}

最后一路推到 a_{n+1},b_{n+1} ，拿到这个式子

(n-n)\cdot f(n+1)=a_{n+1}\cdot f(k+1)+b_{n+1} = 0 \Rightarrow\;f(k+1)=\frac{-b_{n+1}}{a_{n+1}}

如果 a_{n+1}=0 呢？不会的。下证 \forall i\in[k,n),a_{i}<a_{i+1} 。

利用数学归纳法。0=a_k<a_{k+1}=1 。而在 i\in(k,n),a_{i-1}<a_i 时，我们有

a_{i+1}=na_i-ia_{i-1}=a_i+(n-i-1)a_i+i(a_i-a_{i-1})>a_i

所以 a_{n-1}<a_n ，由是则 a_{n+1}=n(a_n-a_{n-1})>0 ，故可行。

话说为什么我想不到题解里面那些简单的做法啊 TAT

代码

这个模数 10^5+3 有几个好处：

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long int_;
inline int readint(){
    int a = 0; char c = getchar(), f = 1;
    for(; c<'0'||c>'9'; c=getchar())
        if(c == '-') f = -f;
    for(; '0'<=c&&c<='9'; c=getchar())
        a = (a<<3)+(a<<1)+(c^48);
    return a*f;
}

const int zxy = 100003;
int inv[zxy], a[zxy], n, dp[zxy];
vector< int > son[zxy];

int main(){
    inv[0] = inv[1] = 1; n = readint();
    for(int i=2; i<zxy; ++i)
        inv[i] = (0ll+zxy-zxy/i)
            *inv[zxy%i]%zxy;
    int k = readint();
    // dp[i] = 1+i*dp[i-1]/n+(n-i)*dp[i+1]/n
    // (n-i)*dp[i+1] = n*dp[i]-n-i*dp[i-1]
    for(int i=0; i<=k; ++i) dp[i] = i;
    int_ a0 = 0, b0 = k, a1 = 1, b1 = 0;
    for(int i=k+1; i<=n; ++i){
        // dp[i-1] = a0*dp[k+1]+b0
        // dp[ i ] = a1*dp[k+1]+b1
        int_ a2 = (n*a1-i*a0)%zxy;
        int_ b2 = (n*b1-n-i*b0)%zxy;
        a2 = (a2*inv[n-i]%zxy+zxy)%zxy;
        b2 = (b2*inv[n-i]%zxy+zxy)%zxy;
        a0 = a1, b0 = b1; // 向前移动
        a1 = a2, b1 = b2; // 向前移动
    }
    dp[k+1] = (zxy-b1)*inv[a1]%zxy;
    for(int i=k+1; i<n; ++i){
        int &t = dp[i+1] = (1ll*n*dp[i]
            -n-1ll*i*dp[i-1])%zxy;
        t = (0ll+t+zxy)*inv[n-i]%zxy;
    }
    for(int i=1; i<=n; ++i)
        a[i] = readint();
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n/i; ++j)
            son[i*j].push_back(i);
    int cnt = 0;
    for(int i=n; i>=1; --i){
        cnt += a[i];
        for(auto j : son[i])
            a[j] ^= a[i];
    }
    int ans = dp[cnt];
    for(int i=1; i<=n; ++i)
        ans = 1ll*ans*i%zxy;
    printf("%d\n",ans);
    return 0;
}