Solution -「六省联考 2017」「洛谷 P3750」分手是祝愿

(mathcal{Description})

  Link.

  有 (n) 盏编号为 (1sim n)，已知初始状态的灯，每次操作选取 (xin[1,n])，使得所有编号为 (x) 的因子的灯的开关状态改变。现在不停地等概率选取 (x) 进行操作，直到在最优策略下能在 (m) 次操作内将所有灯关闭时，则使用最优策略操作。求期望操作次数 ( imes n!) 对 ((10^5+3)) 取模的结果。

(mathcal{Solution})

  最优策略显然是按编号从大到小考虑每盏灯，若开着则对它操作，如此可以求到初始状态下需要操作的灯的集合为 (S)。有结论：

• 若操作 (xin S)，则得到状态的最优操作次数为 (|S|-1)；
• 若操作 (x otin S)，则得到状态的最优操作次数为 (|S|+1)。

利用操作间没有依赖关系的性质，易证。所以我们只需关心 (|S|) 而非 (S)。

  令 (f(i)) 表示 (|S|=i) 时，使得 (|S|=i-1) 的期望操作次数。简单转移即可求出答案。

  我写的是 (mathcal O(nsqrt n))，不难做到 (mathcal O(nln n))。

(mathcal{Code})

/* Clearink */

#include <cmath>
#include <cstdio>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

const int MAXN = 1e5, MOD = 1e5 + 3;
int n, m, a[MAXN + 5], f[MAXN + 5];

inline int add( int a, const int b ) { return ( a += b ) < MOD ? a : a - MOD; }
inline int mul( const long long a, const int b ) { return int( a * b % MOD ); }
inline int mpow( int a, int b ) {
	int ret = 1;
	for ( ; b; a = mul( a, a ), b >>= 1 ) ret = mul( ret, b & 1 ? a : 1 );
	return ret;
}

int main() {
	scanf( "%d %d", &n, &m );
	rep ( i, 1, n ) scanf( "%d", &a[i] );

	int tar = 0;
	per ( i, n, 1 ) if ( a[i] ) {
		++tar;
		rep ( j, 1, int( sqrt( i ) ) ) if ( !( i % j ) ) {
			a[j] ^= 1;
			if ( j * j != i ) a[i / j] ^= 1;
		}
	}

	int ans;
	if ( tar <= m ) ans = tar;
	else {
		ans = m;
		per ( i, n, m + 1 ) {
			f[i] = mul( add( n, mul( n - i, f[i + 1] ) ), mpow( i, MOD - 2 ) ); 
			if ( i <= tar ) ans = add( ans, f[i] );
		}
	}
	rep ( i, 1, n ) ans = mul( ans, i );
	printf( "%d
", ans );
	return 0;
}