crazy_cloud's Blog
0%

AGC013-E Placing Squares

Posted on Edited on In

题目大意

给你一个大小为 \(m\) 的集合 \(S\)。

对于一个所有数和为 \(n\) 的正整数序列 \(\{a_k\}\)，如果 \(\exists 1\leq i\leq k,\sum_{j=1}^ia_i\in S\) 则该序列是非法的。

一个合法的序列的贡献是 \(\prod_{i=1}^ka_i^2\)。给定 \(n,m\) 和 \(S\)，请问所有合法的序列的贡献之和为多少，答案对 \(10^9+7\) 取模。

\(1\leq n\leq 10^9,0\leq m\leq 10^5\)

\(\forall x\in S,1\leq x< n\)

题目分析

还有这种模型转换?.jpg

我们要做一个看起来很平凡但是一下子让题目变得无比简单的神转换。

你有\(n\)个格子排成一排，你要放一些隔板和红蓝两种颜色的球，满足以下条件：

  1. 隔板必须放在格子的左右边界，第一个格子左边和第 \(n\) 个格子右边一定有隔板
  2. 如果 \(i\in S\)，则格子 \(i\) 与 \(i+1\) 之间的间隙不可以放置隔板
  3. 一个格子可以放任意数量任意颜色的球（两种颜色同时放在一格也是可以的）
  4. 一个隔板和它前/后相邻隔板之间必须恰好有一个红球、一个蓝球

求所有放置的方案数。

这个问题显然和原问题等价。然后我们就可以设 \(f_{i,j}\) 表示考虑到第 \(i\) 个格子，在最后一个隔板后面放置了 \(j\) 个球的方案数，转移方程十分好写。

显然能新放隔板和不能新放隔板的转移是两个固定的矩阵。对于集合中相邻两个数之间的空隙，我们使用矩阵快速幂来优化这个转移的过程就好了。

时间复杂度 \(O(m\log n)\)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int M=100005;
const int P=1000000007;

struct matrix
{
	int r,c;
	int num[3][3];

	inline matrix (){r=c=3,memset(num,0,sizeof num),num[0][0]=num[1][1]=num[2][2]=1;}

	inline matrix operator*(matrix const x)const
	{
		matrix ret;
		ret.r=r,ret.c=x.c,memset(ret.num,0,sizeof ret.num);
		for (int i=0;i<ret.r;++i)
			for (int j=0;j<ret.c;++j)
				for (int k=0;k<c;++k)
					(ret.num[i][j]+=1ll*num[i][k]*x.num[k][j]%P)%=P;
		return ret;
	}
}trs,trs_,f;

inline matrix operator^(matrix x,int y)
{
	matrix ret=matrix();
	for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;
	return ret;
}

int x[M];
int n,m,ans;

void calc()
{
	trs.r=trs.c=3;
	trs.num[0][0]=1,trs.num[1][0]=0,trs.num[2][0]=1;
	trs.num[0][1]=2,trs.num[1][1]=1,trs.num[2][1]=2;
	trs.num[0][2]=1,trs.num[1][2]=1,trs.num[2][2]=2;
	trs_.r=trs_.c=3;
	trs_.num[0][0]=1,trs_.num[1][0]=0,trs_.num[2][0]=0;
	trs_.num[0][1]=2,trs_.num[1][1]=1,trs_.num[2][1]=0;
	trs_.num[0][2]=1,trs_.num[1][2]=1,trs_.num[2][2]=1;
	f.r=1,f.c=3,f.num[0][0]=1,f.num[0][1]=f.num[0][2]=0;
	x[0]=0;
	for (int i=1;i<=m;++i) f=f*(trs^(x[i]-x[i-1]-(i>1)))*trs_;
	f=f*(trs^(n-x[m]-(m>0)));
}

int main()
{
	freopen("placing.in","r",stdin),freopen("placing.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<=m;++i) x[i]=read();
	calc(),printf("%d\n",f.num[0][2]);
	fclose(stdin),fclose(stdout);
	return 0;
}