考虑建立异或方程组,则最终状态为该方程组的一个解,第 \(i\) 个方程形如 \(\displaystyle \bigoplus_{i\mid d} x_d=a_i\)。
这些方程构成的向量线性无关,证明如下:
考虑将这些向量从后往前插入线性基。插入第 \(i\) 个向量时,由于已有向量第 \(i\) 位都为 \(0\),故必然能成功插入线性基。
这意味着最终状态惟一,而求出该解只需要类似地从大到小将每个向量插入线性基即可。
由于本题向量的特殊性质,使得线性基每一位对应向量都只有一位有值,可以做到 \(\mathcal O(n\log n)\)
设 \(f(i)\) 表示从需要按下 \(i\) 个按钮到需要按下 \(i-1\) 个按钮的期望步数。
则有
\[\begin{split} f(i)&=\frac in +\frac{n-i}n[f(i+1)+f(i)+1] \\ \\ &=\frac{n+(n-i)f(i+1)}i \end{split}\]边界条件 \(f(n)=1\)
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
using ll=long long;
char buf[1<<14], *p1=buf, *p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in, _tp &x){
x=0; int w=0; char c=GetC();
for(;!isdigit(c);w|=c=='-', c=GetC());
for(;isdigit(c);x=x*10+(c^'0'), c=GetC());
if(w) x=-x;
return in;
}
const int N=1e5+5, mod=100003;
ll a[N], f[N], fac[N], inv[N];
int main(){
int n, k; io>>n>>k;
fac[0]=fac[1]=1; inv[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=1;i<=n;++i) io>>a[i];
int cnt=0;
for(int i=n;i;--i){
for(int j=2*i;j<=n;j+=i) a[i]^=a[j];
cnt+=a[i];
}
f[n]=1;
for(int i=n-1;i;--i){
f[i]=(n+(n-i)*f[i+1])%mod*inv[i]%mod;
}
for(int i=k;i;--i) f[i]=1;
ll ans=0;
for(int i=1;i<=cnt;++i) ans+=f[i];
printf("%lld\n", ans*fac[n]%mod);
return 0;
}
标签:六省,int,GetC,线性,P3750,fac,include,联考,向量
From: https://www.cnblogs.com/pref-ctrl27/p/17110998.html