题解：CF2072F Goodbye, Banker Life

转化为奇偶判定 + Lucas 定理

首先不难发现

f_{i,j}

的取值只可能是

0

或

k

，不妨把

k

看作

1

。那么通过

f_{i,j}

的奇偶性即可确定

f_{i,j}

的值。

由于异或的本质为二进制下的不进位加法，故可以把

f_{i,j}=f_{i-1,j-1} \oplus f_{i-1,j}

转换为

f_{i,j}=f_{i-1,j-1} + f_{i-1,j}

，并把问题转换为判断

f_{i,j}

的奇偶性。

注意到转换后的

f_{i,j}

是杨辉三角。

对于杨辉三角：

当行号和列号均从 0 开始计数：第 $i$ 行第 $j$ 列的取值为 $\binom{i}{j}$ 。
当行号和列号均从 1 开始计数：第 $i$ 行第 $j$ 列的取值为 $\binom{i-1}{j-1}$ 。

由于行号和列号规定均从

1

开始计数，因此对于

f_{i,j}

，它的值就是

\binom{i-1}{j-1}

的值。

那么显然可以用 Lucas 定理秒了。回顾 Lucas 定理：

\binom{i}{j} \equiv \binom{\lfloor \frac{i}{p} \rfloor}{\lfloor \frac{j}{p} \rfloor} \times \binom{i \bmod p }{j \bmod p } \pmod p

那么最终输出第

n

行的第

j

个数时，即输出

\operatorname{lucas}(n-1,j) \times k

。

CPP

int n,k;
int fastpow(int a,int n,int mod){
	int res=1;
	while(n){
		if(n&1) res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}
int getC(int n,int m,int mod){
	int res=1;
	for(int i=n,j=1;j<=m;i--,j++){
		res=res*i%mod;
		res=res*fastpow(j,mod-2,mod)%mod;
	}
	return res;
}
int lucas(int n,int m,int p){
	if(!m) return 1;
	return lucas(n/p,m/p,p)*getC(n%p,m%p,p);
}
void solve(){
	cin>>n>>k;
	rep(i,1,n) cout<<lucas(n-1,i-1,2)*k<<" ";
}

此外还有一个结论做法：

当

\bmod=2

时有一个结论，

\binom{n}{m}

等价于

n \& m ==m

。

也就是说代码还可以这样写：

CPP

int n,k;
int calc(int n,int m){
	return (n&m)==m;
}
void solve(){
	cin>>n>>k;
	rep(i,1,n) cout<<calc(n-1,i-1)*k<<" ";
}

题解：CF2072F Goodbye, Banker Life

文章操作

转化为奇偶判定 + Lucas 定理

相关推荐

评论

题解：CF2072F Goodbye, Banker Life