yukicoder : No.986 Present

うーむややこしい。
https://yukicoder.me/problems/no/986

問題

整数N,Mが与えられる。N≦Mとする。
2^M未満の非負整数N個からなる集合Sを考える。

今、コマが初期位置0にあるとする。
その後、現在地をaとして、Sから任意の要素sを選びa xor sに移動する、ということを任意回数行う。

f(S)は、Sに対してコマが移動できる場所の集合とする。
以下を求めよ。

• 任意のSにおける|f(S)|の最大値。以下これをAとする。
• |f(S)|=Aを達成するSの個数。
• |f(S)|=Aを達成するSに対するf(S)の個数。

解法

1個目は自明で、N個のbit vectorの線形結合で作れるbit vectorの個数を最大化したいので、N≦Mより1 bitずつ立ったvectorをN個作ればA=2^Nとなる。

2個目だが、すでにn個線形独立なベクトルにさらに線形独立なベクトルを足すには、元のn個の線形結合である2^n通り以外のベクトル、(2^M-2^n)通り考えられるので、n=0～(N-1)までこれらの積を取ればよい。
その後、N個の並べ順は任意なのでN!で割る。

3つ目については、同様にN個のベクトルである定められた空間を張る組み合わせなので、同様にn=0～(N-1)まで(2^N-2^n)の積を取りN!で割る。

int N,M;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll p2[303030];
ll fact[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	p2[0]=fact[0]=1;
	FOR(i,301000) {
		p2[i+1]=p2[i]*2%mo;
		fact[i+1]=fact[i]*(i+1)%mo;
	}
	
	cout<<p2[N]<<" ";
	ll ret=modpow(fact[N]);
	FOR(i,N) ret=ret*(p2[M]-p2[i]+mo)%mo;
	cout<<ret<<" ";
	
	ll ret2=1;
	FOR(i,N) ret2=ret2*(p2[N]-p2[i]+mo)%mo;
	(ret2*=modpow(fact[N]))%=mo;
	cout<<(ret*modpow(ret2))%mo<<endl;
	
	
	
}

まとめ

結果だけ見るとシンプルなんだよね。