首页 > 其他分享 >[GXOI/GZOI2019] 逼死强迫症 题解

[GXOI/GZOI2019] 逼死强迫症 题解

时间:2024-09-27 12:13:55浏览次数:7  
标签:matrix 题解 sum 强迫症 long times GZOI2019 dp 方砖

看到 \(N\leq 2\times 10^9\) 的范围,一眼矩阵快速幂优化 DP

首先考虑朴素 DP 怎么写。根据题目所给信息,我们设 \(dp_{i,0}\) 表示前面 \(i\) 个方砖,并且已经使用了 \(2\) 个 \(1\times 1\) 的方砖,\(dp_{i,1}\) 则表示前面 \(i\) 个方砖,没有使用任何一个 \(1\times 1\) 的方砖。

为了转移至 \(dp_{i,0}\),既然已经使用过了 \(2\) 个 \(1\times 1\) 的方砖,那么我们剩下的都是 \(1\times 2\) 的方砖,对于这样的方砖,我们有两种可行的摆放,一种是直接竖着放,可以由 \(dp_{i-1,0}\) 转移得到;另一种是两个横着放,可以由 \(dp_{i-2,0}\) 得到。而我们还可以在 \([1,i-3]\) 选择一个 \(j\),然后利用后面的区间 \([j+1,i]\) 放置两个 \(1\times 1\) 的方砖,且两个方砖放置的位置分别在第 \(j+1\) 列和第 \(i\) 列。而我们不难发现有两种情况,一种是这个区间长度为奇数,另一种是区间长度为偶数。

对于奇数长度的区间,我们可以让两个方砖放在不同的行,这里各自的行剩下的长度就是偶数(奇数减一是偶数),我们就每行横着放 \(1\times 2\) 的方砖就可以了。而如果放在同一行,那么我们就无法填满里面的空缺(可以自己画图理解一下)。对于偶数长度的区间,我们可以让两个方砖在同一行,这样上下两行剩余的长度就都是偶数了,就可以横着放 \(1\times 2\) 的方砖来填满空缺,反之如果是在不同的行,那么我们就不可以完成。

如果实在理解不了,我可以给一点提示,就是当区间两边填了 \(1\times 1\) 的方砖后,那么对于所填方砖的另外一行,我们只可能使用 \(1\times 2\) 的方砖填满那个 \(1\times 1\) 的空缺,而此时又会产生新的 \(1\times 1\) 的空缺……以此类推。(这样提示还不够,那我可能就帮不了你了。。)

总之我们可以发现,不管是放在不同的行或者相同的行,都会得到 \(2\) 种答案。而且此时我们转移的是 \(dp_{j,1}\),因为如果在 \([j+1,i]\) 放置两个裂开的砖块,那么 \([1,j]\) 肯定就是没有裂开的砖块的。

而我们的 \(dp_{i,1}\) 就非常好转移了,就是要么竖着放,要么两个横着放,即 \(dp_{i,1}=dp_{i-1,1}+dp_{i-2,1}\)。

所以我们列出方程:

\[\begin{cases} dp_{i,0}=dp_{i-1,0}+dp_{i-2,0}+2\times \sum _{j=1}^{i-3}dp_{j,1}\\ dp_{i,1}=dp_{i-1,1}+dp_{i-2,1} \\\end{cases} \]

但是这样肯定是会超时的,所以就会想到使用矩阵

但是我们又发现这个 \(dp_{i,0}\) 的转移不是 \(O(1)\) 的,所以考虑将方程进行改造。对于 \(\sum _{j=1}^{i-3}dp_{j,1}\),我们不难发现每次 \(i\) 增加 \(1\),我们原来的值就会增加一个 \(dp_{j,1}\) 的值。根据这个形式,我们就想到使用前缀和储存这个区间值。设 \(sum_i\) 表示 \(\sum_{j=1}^i dp_{j,1}\) 的值。原方程变为:

\[dp_{i,0}=dp_{i-1,0}+dp_{i-2,0}+2\times sum_{i-3} \]

我们将一次转移使用到的值提出来:\(dp_{i-1,0}\),\(dp_{i-2,0}\),\(sum_{i-3}\),\(dp_{i-1,1}\),\(dp_{i-2,1}\)。然后利用这些值构造初始矩阵:

\[\left( \begin{matrix} dp_{i-1,0} & dp_{i-2,0} & dp_{i-1,1} & dp_{i-2,1} & sum_{i-3} \end{matrix} \right) \]

换成具体的数值,真正的初始矩阵是:

\[\left( \begin{matrix} 0 & 0 & 2 & 1 & 1 \end{matrix} \right) \]

注意这个 \(sum_0\) 是 \(1\),因为放置 \(0\) 个方砖也是一种答案。

每次转移按照上述方程进行转移,得到转移矩阵:

\[\left( \begin{matrix} 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 2 & 0 & 0 & 0 & 1 \end{matrix} \right) \]

所以得到答案为:

\[\left( \begin{matrix} 0 & 0 & 2 & 1 & 1 \end{matrix} \right) \times \left( \begin{matrix} 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 2 & 0 & 0 & 0 & 1 \end{matrix} \right) ^{n-2} \]

这样代码就非常简单了:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
long long n,p,q;
void mul(long long f[5],long long a[5][5])
{
    long long c[5];
    memset(c,0,sizeof(c));
    for(int j=0;j<5;j++)
    {
    	for(int k=0;k<5;k++)	c[j]=(c[j]+f[k]*a[k][j])%MOD;
	}
    memcpy(f,c,sizeof(c));
}
void mulself(long long a[5][5])
{
    long long c[5][5];
    memset(c,0,sizeof(c));
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            for(int k=0;k<5;k++)    c[i][j]=(c[i][j]+(long long)a[i][k]*a[k][j])%MOD;
        }
    }
    memcpy(a,c,sizeof(c));
}
signed main()
{
	long long T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		long long f[5]={0,0,2,1,1};
		long long a[5][5]={0};
		a[0][0]=a[0][1]=a[1][0]=a[2][2]=a[2][3]=a[3][2]=a[3][4]=a[4][4]=1,a[4][0]=2;
		if(n==1||n==2||!n)
		{
			puts("0");
			continue;
		}
		n-=2;
		while(n)
		{
			if(n&1)	mul(f,a);
			mulself(a);
			n>>=1;
		}
		cout<<f[0]<<endl;
	}
	return 0;
}

标签:matrix,题解,sum,强迫症,long,times,GZOI2019,dp,方砖
From: https://www.cnblogs.com/SuporShoop/p/18435409

相关文章

  • [CERC2015] Digit Division 题解
    \(O(n^2)\)做法和大部分人最开始一样,我也想的是DP。设\(dp_i\)表示用前面\(i\)个字符拆分得到的答案。既然是统计方案数,我们肯定是根据前面的答案累加。考虑在\([1,i-1]\)中选择一个\(j\),如果\([j+1,i]\)的字符组成的数字能够被\(m\)整除,那么\(dp_i\)就可以累加......
  • [JLOI2015] 有意义的字符串 题解
    拿到题目,我们首先分析一下这个奇怪的式子:\[\lfloor(\frac{b+\sqrt{d}}{2})^n\rfloor~\text{mod}~p\]重点肯定是在里面的那个式子里面,最显眼的肯定也就是那个\(\sqrt{d}\),根据整体形式,我们可以联系一元二次方程的求根公式\(x=-\dfrac{-b\pm\sqrt{b^2-4ac}}{2a}\),这里也是一......
  • 「KDOI-06-S」消除序列 题解
    分享一个应该很少人想到的做法。首先贪心地想,第一种操作肯定最多选择一次。比如如果选择了下标\(i\)和\(j\)进行第一种操作,那么就等价于在\(\max\{i,j\}\)进行了一次操作。由于代价是非负数,则我们最多只用执行一次。当然也可以不使用这种操作。有了这个思路,我们先考虑不使......
  • 「TAOI-2」Ciallo~(∠・ω< )⌒★ 题解
    手玩了一个小时终于做出来了,这不得写一篇题解记录一下??下面设\(s\)的长度为\(n\),\(t\)的长度为\(m\)。考虑分类讨论:如果\(s\)中有一个子串\(s'\)与\(t\)完全相同(可以用哈希进行比较),设\(s'\)是\(s\)的第\(l\)到第\(r\)个字符组成的字符串,则我们可以删除\([1,......
  • 三星G8 OLED显示器S34BG850SC,使用DP线连接电脑,显示器黑屏问题解决。
    这个问题在网上好像很多人问,但是每个人的情况不同,总之我也是遇到了。事情大概:PC机显卡的DP口通过显示器自带的MiniDP线和显示器相连,这个没什么好说的了,原配只送MiniDP线,想必买这台显示器的人都是先用的这根线。然而我有一台NUC,通过雷电口也连接到了这台显示器。所以我这台G8是......
  • [TJOI2010] 天气预报 题解
    分析一下题目,大致意思就是给定一组常数\(a_i\),然后有一个递推式\(w_i=\sum_{j=1}^{n}w_{i-j}\timesa_{j}\),让你求出\(w_m\)对于\(4147\)取模的值。根据这个\(1\leqm\leq10^7\)的恐怖范围,姑且算到了\(O(m)\)的时间复杂度。但是观察一下这个递推式,发现\(O(m)\)跑......
  • ABC262G 题解
    LISwithStack观察到\(n\le50\),考虑区间dp。设\(dp(l,r,x,y)\)表示区间\([l,r]\)中选出的子序列的最小值\(\gex\),最大值\(\ley\)的方案数。根据栈的性质,设元素\(x\)入栈的时间为\(in_x\),出栈时间为\(out_x\),那么所有元素构成的区间\([in_x,out_x]\)两......
  • 2024-2025专题二题单 - 题解
    A-MoneyinHand(记忆化搜索)原题链接题解B-GoodGraph(并查集)原题链接题解C-IceSkating(dfs求连通块)原题链接题解D-TheLakes(dfs求连通块,连通块内累加,多组数据注意初始化)原题链接题解E-LearningLanguages(建图,dfs统计连通块个数,答案为个数-1)原题链接题......
  • 进击的奶牛题解
    题目描述FarmerJohn建造了一个有 N(2≤N≤105)个隔间的牛棚,这些隔间分布在一条直线上,坐标是 x1,x2,⋯ ,xN​(0≤xi≤109)。他的 C(2≤C≤N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,FarmerJohn想把这些牛安置在指定的隔间,所......
  • 奶牛分厩题解
    题目描述农夫约翰有 N(1≤N≤5000)头奶牛,每头奶牛都有一个唯一的不同于其它奶牛的编号 s[i],所有的奶牛都睡在一个有 K 个厩的谷仓中,厩的编号为 00 到 K−1。每头奶牛都知道自己该睡在哪一个厩中,因为约翰教会了它们做除法,Si mod K的值就是第 i 头奶年所睡的厩的编......