题目大意
题目描述
在这道题中，你将有一个$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;
}
|
