CF1332E Height All the Same 题解

可以用生成函数和多项式取模做。本质上和矩阵乘法差不多，但是更好写。

观察发现，若所有位置奇偶性相同，则用操作二可以做到合法。操作一可以看作反转相邻两个位置的奇偶性。

当且仅当奇数高度位置的个数为奇数个，且偶数高度位置的个数为奇数个，无解。否则有解。

按照

n \times m

的奇偶性分类讨论。只有

2 \mid n \times m

时可能出现上述无解情况。

只需要求，

n \times m

个位置，每个位置可以填

A

种奇数，或者

B

种偶数。求填奇数的位置有偶数个，的方案数。

生成函数

f(x) = ax+b

，

[x^1]

表示填奇数的位置有奇数个的方案数，

[x^0]

表示填奇数的位置有偶数个的方案数。

需要求

[x^0] (Ax+B)^{n\times m} \pmod{x^2-1}

。注意是多项式取模。

其实不需要会多项式取模，只是在多项式快速幂的过程中，把

x^2

换成

x^0

。因为

0,2

奇偶性相同。

不用动脑子而且比矩阵好写一点。

CPP

#include<bits/stdc++.h>
#define sf scanf 
#define pf printf 
#define rep(x,y,z) for(int x=y;x<=z;x++) 
#define per(x,y,z) for(int x=y;x>=z;x--) 
using namespace std;
typedef long long ll;
namespace wing_heart {
	constexpr int mod=998244353;
	struct modint {
		int x;
		modint (int y=0) : x(y) {} 
		modint operator + (modint b) const { return x+b.x<mod ? x+b.x : x+b.x-mod; }
		modint operator * (modint b) const { return 1ll*x*b.x%mod; }
		modint &operator += (modint b) { return *this = *this + b; } 
		modint &operator *= (modint b) { return *this = *this * b; } 
	};
	modint ksm(modint a,ll b) {
		modint s=1;
		while(b) {
			if(b&1) s*=a;
			a*=a;
			b>>=1;
		}
		return s;
	}
	struct poly {
		modint x1,x0;
		poly operator + (poly b) const { return {x1+b.x1,x0+b.x0}; }
		poly operator * (poly b) const { return {x1*b.x0+x0*b.x1,x0*b.x0+x1*b.x1}; }
		poly &operator += (poly b) { return *this = *this + b; }
		poly &operator *= (poly b) { return *this = *this * b; }
	};
	poly ksm_poly(poly a,ll b) {
		poly s = {0,1};
		while(b) {
			if(b&1) s*=a;
			a*=a;
			b>>=1;
		}
		return s;
	}
	int n,m,l,r;
	int A,B;
	int solve() {
		poly t = ksm_poly({A,B},1ll*n*m);
		return t.x0.x;
	}
	void main() {
		sf("%d%d%d%d",&n,&m,&l,&r);
		if((1ll*n*m)&1) pf("%d\n",ksm(r-l+1,1ll*n*m).x), exit(0);
		if((l&1)^(r&1)) A=B=(r-l+1)>>1;
		else if(l&1) A=(r-l+2)>>1, B=(r-l)>>1;
		else A=(r-l)>>1, B=(r-l+2)>>1;
		pf("%d\n",solve());
	}
}
int main() {
	wing_heart :: main();
}

CF1332E Height All the Same 题解

文章操作

相关推荐

评论

CF1332E Height All the Same 题解