P3750 [六省联考2017]分手即是祝愿
Zeit und Raum trennen dich und mich. 时空将你我分开。
这个题目名字不错，我非常喜欢（（（
首先考虑一个开关绝不会被其他组合的开关所替代。也就是说对给定的一个组合，有几个开关是必须按的，其余的则是必须不按的。这是解题的一条关键性质。
再考虑，对当前组合我们如何求出哪些开关要按，而哪些不用按。有一个朴素的想法，从 n 开始每扫到一个亮着的开关，就对其进行操作。根据上面一条性质，我们得到了有多少个开关是必须按的。
最后我们考虑如何求期望步数。
这个就有点骚了。
所实话，我一开始是这么想的，设 dp[i] 为当前局面还有 i 个开关需要按，然后到达全灭状态的期望步数。那么有转移为
[dp[i]=frac{i}{n} imes dp[i-1]+1+frac{n-i}{n} imes dp[i+1]
]
然后高斯消元即可，由于这玩意是个带状矩阵，所以可以 (O(n)) 消元。做法大概和 Broken Robot 相同
但是题解里面提到一种奇妙的做法
我们的状态是到达终点的状态，而他设的则是
(dp[i]) 为 (i) 个需要按的开关到 (i-1) 个需要按的开关这两个局面之间的期望步数。
于是有
[dp[i]=frac{i}{n}+(1-frac{i}{n}) imes(dp[i+1]+1+dp[i])
]
前一部分是恰好选中了那 (i) 个键。（这个很好理解
后一部分则是没选中那 (i) 个键，首先你需要 (1) 步来进行错误操作弄到 (i+1) 步
然后再算上 (dp[i+1]) 和 (dp[i]) 即可。
然后化简一下就行。
（判当前步数小于 (k) 竟然有 (75pts)，我很奇怪出题人怎么造的数据
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1ll<<30
template<typename _T>
inline void read(_T &x)
{
x=0;char s=getchar();int f=1;
while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
x*=f;
}
const int np = 1e5 + 5;
const int mod = 1e5 + 3;
int a[np],Ans;
int dp[np];
int fac[np];
int n , k;
inline void solve()
{
int op = 0;
for(int i=n;i>=1;i--)
{
if(a[i])
{
int sqt = sqrt(i);
for(int j = 1;j<=sqt;j++)
{
if(i % j == 0)
{
a[j] ^= 1;
if(j != i / j) a[i / j] ^= 1;
}
}
Ans ++ ;
}
}
}
inline int power(int a,int b)
{
int res = 1;
while(b)
{
if(b & 1) res = res * a,res %= mod;
a = a * a;
a %= mod;
b >>= 1;
}
return res;
}
inline int inv(int i)
{
return power(i,mod-2);
}
signed main()
{
read(n);
read(k);
fac[0] = 1;
for(int i=1;i<=n;i++) fac[i] = fac[i - 1] * i % mod;
for(int i=1;i<=n;i++) read(a[i]);
solve();
dp[n] = 1;
for(int i=n - 1;i>= k + 1;i--)
{
int invi = inv(i);
dp[i] = (((((n - i) * invi)%mod) *dp[i + 1]) % mod) + ((n*invi)%mod);
dp[i] %= mod;
}
if(Ans <= k)
{
cout<<(Ans * fac[n]) % mod;
return 0;
}
int sum(0);
for(int i=k + 1;i<=Ans;i++) sum += dp[i],sum %= mod;
sum += k;
sum %= mod;
sum *= fac[n];
sum %= mod;
cout<<sum;
}
总的来说，这个题的第一个性质很神仙（反正我是没想到
这个 (dp) 状态很神仙（虽然说用高斯消元也行
题目名字很神仙（这名字我直接吹爆，能和『谈笑风生』五五开了。