2745: [HEOI2012]Bridge
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 199 Solved: 90
[Submit][Status][Discuss]
Description
fyg背着他的电脑来到河北省来，就是为了见一眼古老的赵州桥。
终于，他来到了赵州桥，放下了电脑，正准备休息。一阵风吹来，从中闪现出一人影。fyg只觉天昏地暗，待得再次睁开眼时，发觉自己已经到了一神奇的国度，置身于一巨大的圆盘之上。放眼看去，四周都是奇形怪状的桥，不远处有一老头盘膝而坐。 fyg还沉浸在惊奇之中，老头（难道就是传说中走过赵州桥的张老头！！）便开口了：凡人，你现在在我的世界中，想要出去就要回答我的问题。fyg只得点头，老头继续道：你现在要去闯关，我给你m种颜色，总共有n关（神仙也懂数学，表示压力巨大。。==）。每一关中有一座桥，在第i关中，桥长度有i个单位，每个单位长度上有2个格子（也就是说这座桥有2i个格子），现在你要计算出：在这座桥上涂色使得桥上相邻格子的颜色不一样总方案数，然后再乘上（2*i）^m。如在第1关，若你手上有2种颜色，分别为蓝色和绿色。则总方案数为2*2*2 =8种，涂色方案数为2（如下图，旋转、翻转相同算不同的方案），然后还要再乘2个2，最后你出来之后我会问你所有关中计算出来的数的和。如果你能答对，我就可以让你出去了，否则就无限轮回吧。
fyg表示这个问题太水了，完全不想算。。。于是， 他马上打开电脑上了QQ找到了喜欢计算的你，求你 帮他直接把最终 答案算出来，让他回到赵州桥上。这两个数都有可能很大，fyg 不想为难你，所以你只要告诉他其除以p的余数。
Input
只有一行，其中包含四个正数n、m、p，分别由一个空格分开。n、m、p含义和题目描 述一致。
Output
一行，表示方案数的和除以p的余数。
Sample Input
Sample Output
【样例说明】
总共有2关。
第一关的桥长度为1，总共有2个格子，涂色方案数为20，再乘上2 ^ 5，第一关中 计算出的数为640。
第二关的桥长度为2，总共有4个格子，涂色方案数为260，再乘上4 ^ 5，第二关中 计算出的数为266240。
两个数字加起来除以50余30，故输出为30。
HINT
【数据范围】
对于其中25%的数据，满足 n <= 10^6，m <= 200，p <= 10^9； 对于其中40%的数据，满足 n <= 10^9，m <= 120，p <= 10^9； 对于其中15%的数据，满足 n <= 10^9，m <= 200，p <= 10^9； 对于最后20%的数据，满足 n<= 10^9，m <= 3000，p <= 3000；
Source
写了一天的二逼题，KCUF
首先说一下，题目中的桥是2xN的，而不是1x2N的，别想错了，不然就真的走远了。
然后可以手推一下样例，发现是个简单的DP，甚至连DP都称不上，就是个统计问题，这时你应该得到了一个式子——
$answer=2^{m}(m^{2}-m)\sum_{i=1}^{n}{i^{m}(m^{2}-3m+3)^{i-1}}$，推不出来还是洗洗睡吧。
然后看到数据范围，发现有25points是给暴力的，$O(NlogM)$就可以拿到。
然后看出下面的数据要分两种做法——一种针对m较大但是p较小的，一种针对m较小但是p很大的。
m较大，p较小
发现$i^{m}$这一项，在$mod p$意义下有很有意思的性质——$i^{m}=(i mod p)^{m}$。
哎，那岂不是至多每p项$i^{m}$就会出现一个循环吗？而每个循环节之间又是$(m^{2}-3m+3)^{p}$的等比关系（在此默认循环节长度为p），那就暴力求出第一段和公比，就是等比数列求和。蛋疼的是p不一定是素数，所以想用等比公式是不行的，因为没有逆元。然后就可以倍增法或矩阵快速幂。（小生一开始写的倍增，结果越写越乱，最后还是用矩阵幂省心）
m较小，p较大
还是想法搞掉$i^{m}$这一项。发现$i^{m}=[(i-1)+1]^{m}$，然后可以二项式一下就可以搞成DP形式了，$f[i][j]=i^{j}(m^{2}-3m+3)^{i-1}$，f[i]可以从f[i-1]推出来，构造转移矩阵，跑矩阵快速幂并维护前缀和即可。
#include <cstdio>
#include <cstring> typedef long long lnt; int n, m, p; inline int pow(lnt a, int b)
{
lnt r = ; while (b)
{
if (b & )
r = r * a % p; b = b >> ;
a = a * a % p;
} return r;
} namespace case1
{ // m <= 200
int lim;
int ans; int C[][]; inline void calculateC(void)
{
for (int i = ; i <= lim; ++i)
{
C[i][] = ; for (int j = , k = ; j <= i; j += , k += )
{
C[i][j] = C[i - ][j - ] + C[i - ][j];
C[i][k] = C[i - ][k - ] + C[i - ][k]; if (C[i][j] >= p)C[i][j] -= p;
if (C[i][k] >= p)C[i][k] -= p;
}
}
} int M[][]; inline void calculateM(void)
{
int bas = (m * m - *m + ) % p; for (int i = ; i <= m; ++i)
for (int j = i; j <= m; ++j)
M[i][j] = 1LL * bas * C[j][i] % p; M[m][lim] = M[lim][lim] = ;
} int R[]; inline void calculateR(void)
{
for (int i = ; i <= m; ++i)R[i] = ; for (int t = n; t; t >>= )
{
if (t & )
{
static int T[]; memset(T, , sizeof T); for (int i = ; i <= lim; ++i)
for (int j = ; j <= lim; ++j)
T[j] = (T[j] + 1LL * R[i] * M[i][j]) % p; memcpy(R, T, sizeof R);
} {
static int T[][]; memset(T, , sizeof T); for (int i = ; i <= lim; ++i)
for (int k = ; k <= lim; ++k)if (M[i][k])
for (int j = ; j <= lim; ++j)if (M[k][j])
T[i][j] = (T[i][j] + 1LL * M[i][k] * M[k][j]) % p; memcpy(M, T, sizeof M);
}
}
} inline void main(void)
{
lim = m + ; calculateC();
calculateM();
calculateR(); ans = R[lim]; ans = (1LL * ans * pow(, m)) % p;
ans = (1LL * ans * (m*m - m)) % p; printf("%d\n", (ans + p) % p);
}
} namespace case2
{ // p <= 3000
int bas;
int cnt;
int ans; int C[]; inline void calculateC(void)
{
bas = (m * m - *m + ) % p; for (int i = , t = ; i <= p; ++i, t = t * bas % p)
C[] = (C[] + pow(i, m) * t) % p;
} int M[][]; inline void calculateM(void)
{
M[][] = pow(bas, p);
M[][] = ;
M[][] = ;
M[][] = ;
} int R[][]; inline void calculateR(void)
{
memcpy(R, C, sizeof C); for (int t = cnt; t; t >>= )
{
if (t & )
{
static int T[][]; memset(T, , sizeof T); for (int i = ; i < ; ++i)
for (int k = ; k < ; ++k)if (R[i][k])
for (int j = ; j < ; ++j)if (M[k][j])
T[i][j] = (T[i][j] + R[i][k] * M[k][j]) % p; memcpy(R, T, sizeof R);
} {
static int T[][]; memset(T, , sizeof T); for (int i = ; i < ; ++i)
for (int k = ; k < ; ++k)if (M[i][k])
for (int j = ; j < ; ++j)if (M[k][j])
T[i][j] = (T[i][j] + M[i][k] * M[k][j]) % p; memcpy(M, T, sizeof M);
}
}
} inline void main(void)
{
cnt = n / p; calculateC();
calculateM();
calculateR(); ans = R[][]; for (int i = cnt * p + ; i <= n; ++i)
ans = (ans + pow(i % p, m) * pow(bas, i - )) % p; ans = (1LL * ans * pow(, m)) % p;
ans = (1LL * ans * (m*m - m)) % p; printf("%d\n", (ans + p) % p);
}
} signed main(void)
{
scanf("%d%d%d", &n, &m, &p); if (m <= )
case1::main();
else
case2::main();
}
@Author: YouSiki