「cdqzD12T1」矩阵染色 - 数学+解方程+分类讨论 | Bill Yang's Blog
0%

「cdqzD12T1」矩阵染色 - 数学+解方程+分类讨论

题目大意

题目描述

    在这道题中,你将有一个$2$行若干列的矩阵,你需要用$m$种不同的颜色为其染色(不一定全部用上),使得相邻的格子颜色不同(这里的两个格子相邻指有公共边)。设$2\times i$的矩阵的染色方案数为$f(i)$,请你求$\sum_{i=1}^nf(i)(2i)^m$对$p$取模的结果。

数据范围

测试点编号 $n$ $m$ $p$
$[1,4]$ $\le10^5$ $\le10^5$ $\le10^9$
$[5,12]$ $\le10^9$ $\le100$ $\le10^9$
$[13,16]$ $\le10^9$ $\le10^5$ $\le1000$
$[17,20]$ $\le10^9$ $\le1000$ $\le10^9$

题目分析

用动态规划+数学知识不难得出:

故所求答案为:

令$t=m^2-3m+3$,故答案变为$\frac{2^m(m^2-m)}t\sum_{i=1}^nt^ii^m$。
令$S(n,m)=\sum_{i=1}^nt^ii^m$,故求出$S(n,m)$即可快速得出答案。

对于第一部分的数据,可以直接暴力求。
对于第二部分的数据,我们考虑递推求$S(n,m)$。

这样我们就可以构造一个$m\times m$的矩阵进行快速幂即可。
对于第三部分的数据,观察到$p$很小,尝试将原式的枚举转化到$p$范围以内。
因此我们可以将$S(n,m)$作个简单的变形:

这样我们只需要枚举到$p$,后面部分等比数列求和即可。
时间复杂度$O(p\log n)$,比标解的找循环节更优。

对于第四部分的数据,我们考虑在$O(m^2)$的时间内解决。
不妨用另一种方式写出$S(n,m)$的递推式。

结合上述矩阵快速幂时用到的递推式,我们可以得出方程:

因此可得:

这样我们就可以在$O(m^2)$的时间内推出$S(n,m)$。

综上,我们可以通过四种方法分段得到全部部分分。


题目总结

本题很有意思,有两点可以进行总结。

  • 对于一些求和式,若要从$f(n-1)$快速递推得到$f(n)$,可以考虑两种方式,第一种方式是将$f(n)$写为$f(n-1)+b$的形式,这也是最常用的,另一种方式是提出第一项,将之前的所有项集体右移,也就是将$\sum_{i=1}^{n+1} g(i)$写成$\sum_{i=1}^n g(i+1)+g(1)$的形式。
  • 若要求快速计算一些含有取模$p$与枚举$i\in[1,n]$的式子,我们可以按照模$p$的剩余系进行分段,考虑每一段一起统计能否加速。

代码

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
74
75
76
77
78
79
80
81
82
83
84
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

LL n,m,p;

LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;
return sum;
}

LL inv(LL a) {
return Quick_Pow(a,p-2);
}

namespace PrimeBase {
void solve() {
LL sum=0,t=((m*m%p-3*m+3%p)%p+p)%p;
for(int i=0; i<=min(p-1,n); i++) {
int N=(n-i)/p+1;
sum=(sum+Quick_Pow(i,m)*Quick_Pow(t,i)%p*inv(((Quick_Pow(t,p)-1+p)%p))%p*((Quick_Pow(t,p*N)-1+p)%p))%p;
}
printf("%lld\n",sum*Quick_Pow(2,m)%p*((m*m-m)%p)%p*inv(t)%p);
}
}

namespace Equation {
const int maxm=1005;

LL C[maxm][maxm],f[maxm];

void Get_C() {
for(int i=0; i<=m; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<i; j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
}
}

void solve() {
Get_C();
LL t=((m*m%p-3*m+3%p)%p+p)%p;
f[0]=t*inv(t-1)%p*(Quick_Pow(t,n)-1)%p;
for(int i=1; i<=m; i++) {
LL sum=0;
for(int j=0; j<i; j++)sum=(sum+C[i][j]*f[j]%p)%p;
f[i]=((Quick_Pow(t,n+1)*Quick_Pow(n+1,i)%p-t-sum*t%p)%p+p)%p*inv(t-1)%p;
}
printf("%lld\n",f[m]*Quick_Pow(2,m)%p*((m*m-m)%p)%p*inv(t)%p);
}
}

int main() {
n=Get_Int();
m=Get_Int();
p=Get_Int();
if(m>1000)PrimeBase::solve();
else Equation::solve();
return 0;
}
姥爷们赏瓶冰阔落吧~