首页 > 其他分享 >AGC013E

AGC013E

时间:2022-11-02 09:00:31浏览次数:58  
标签:AGC013E mat 格子 隔板 int res ++

模型转化题,转化不出来就白给。

可以把题目的条件翻译成以下组合语言:

  • 有一排 \(n\) 个格子,你要在其中插入若干个隔板将其隔成若干段
  • 有 \(m\) 个特殊格子 \(a_1,a_2,\dots,a_m\),\(\forall i\in [1,m]\) 你禁止在 \(a_i\) 与 \(a_{i}+1\) 之间放隔板
  • 在相邻隔板之间的格子中需恰好放上两个不同的球(可以重合)

不难发现,上述题面中的”隔板“对应原题中的正方形边界,对于一段长度为 \(l\) 的段,在上面放两个不同的球的方案数为 \(l^2\),也就对应了原题面中的”平方“,而原题中的乘法在上述题面中被翻译成了乘法原理。因此我们就将这题与组合意义联系在了一起。

设 \(f_{i,j}\) 表示现在考虑了前 \(i\) 个位置,在当前位置到上一个隔板的区间中放上了 \(j\) 个球的方案数,其中 \(j\in [0,2]\)。

对于非特殊格子 \(i\) 我们有状态转移方程:

  • \(f_{i+1,0}=f_{i,0}+f_{i,2}\)
  • \(f_{i+1,1}=(2f_{i,0}+f_{i+1,1})+2f_{i,2}\)
  • \(f_{i+1,2}=(f_{i,0}+f_{i,1}+f_{i,2})+f_{i,2}\)

注意这里将不放隔板的转移都放在了前面,放隔板的转移都放在了后面。

对于特殊格子的话状态转移方程只要把放隔板的转移去掉就行了。

不难发现这可以写成矩阵形式。

时间复杂度 \(\mathcal O(m\log n\omega^3)\),其中 \(\omega=3\)。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int n, m;
struct mat {
	int a[3][3];
	
	mat (){}
	void clear() { memset(a, 0, sizeof a); }
	void init() { clear(); for (int i = 0; i < 3; ++i) a[i][i] = 1; }
	mat operator * (const mat &x) const {
		mat res; res.clear();
		for (int i = 0; i < 3; ++i)
			for (int j = 0; j < 3; ++j)
				for (int k = 0; k < 3; ++k)
					res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * x.a[k][j] % mod) % mod;
		return res;
	}
} f, x, y;

mat qpow(mat x, int y) {
	mat res; res.init();
	while (y) {
		if (y & 1) res = res * x;
		x = x * x;
		y >>= 1;
	}
	return res;
}

int main() {
	f.a[0][0] = 1;
	x.a[0][0] = 1, x.a[0][1] = 0, x.a[0][2] = 1;
	x.a[1][0] = 2, x.a[1][1] = 1, x.a[1][2] = 2;
	x.a[2][0] = 1, x.a[2][1] = 1, x.a[2][2] = 2;
	y.a[0][0] = 1, y.a[0][1] = 0, y.a[0][2] = 0;
	y.a[1][0] = 2, y.a[1][1] = 1, y.a[1][2] = 0;
	y.a[2][0] = 1, y.a[2][1] = 1, y.a[2][2] = 1;
	scanf("%d%d", &n, &m); int lst = -1; 
	for (int i = 1, cur; i <= m; ++i) {
		scanf("%d", &cur);
		f = qpow(x, cur - lst - 1) * f, f = y * f, lst = cur;
	}
	f = qpow(x, n - lst - 1) * f;
	printf("%d", f.a[2][0]);
	return 0;
}

标签:AGC013E,mat,格子,隔板,int,res,++
From: https://www.cnblogs.com/Kobe303/p/16849839.html

相关文章

  • AT2371 [AGC013E] Placing Squares
    AT2371[AGC013E]PlacingSquares设\(f_i\)表示考虑到第\(i\)个点的贡献之和且不考虑坏点。不难发现转移方程为\(f_n=\sum_{i=0}^nf_i\times(n-i)^2\)则当第\(n......