http://acm.hdu.edu.cn/showproblem.php?pid=2604
这题居然O(9 * L)的dp过不了，TLE, 更重要的是找出规律后，O（n）递推也过不了，TLE,一定要矩阵快速幂。然后立马GG.
用2代表m，1代表f。设dp[i][j][k]表示，在第i位，上一位站了的人是j，这一位站的人是k，的合法情况。
递推过去就是，如果j是1，k是2，那么这一位就只能放一个2，这个时猴dp[i][k][2] += dp[i - 1][j][k];
其他情况分类下就好，然后乖乖超时吧。注意L = 1的时候，直接是2
或者直接dfs搜也行。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int L, MOD;
const int maxn = 1e6 + ;
LL quick_pow(LL a, LL b, LL MOD) {
LL base = a % MOD;
LL ans = ;
while (b) {
if (b & ) {
ans = (ans * base) % MOD;
}
base = (base * base) % MOD;
b >>= ;
}
return ans;
}
int dp[][][];
//int dfs(int cur, int one, int sec) {
// if (cur == L + 1) return 0;
// if (vis[cur][one][sec] == DFN) return dp[cur][one][sec];
// vis[cur][one][sec] = DFN;
// int ans = 0;
// if (one == 1 && sec == 2 || one == 1 && sec == 1) {
// ans += quick_pow(2, L - cur, MOD);
// ans += dfs(cur + 1, sec, 2);
// ans %= MOD;
// } else {
// ans += dfs(cur + 1, sec, 1);
// ans += dfs(cur + 1, sec, 2);
// ans %= MOD;
// }
// dp[cur][one][sec] = ans;
// return ans;
//}
void work() {
// DFN++;
if (L == ) {
printf("0\n");
return;
}
if (L == ) {
printf("1\n");
return;
}
// int ans = (quick_pow(2, L, MOD) + MOD - dfs(1, 0, 0)) % MOD;
// printf("%d\n", ans);
// printf("******%d\n", dfs(1, 0, 0));
memset(dp, , sizeof dp);
dp[][][] = ;
int now = ;
for (int i = ; i <= L; ++i) {
now = !now;
memset(dp[now], , sizeof dp[now]);
for (int j = ; j <= ; ++j) {
for (int k = ; k <= ; ++k) {
if (j == && k == || j == && k == ) {
dp[now][k][] += dp[!now][j][k];
if (dp[now][k][] >= MOD) dp[now][k][] %= MOD;
} else {
dp[now][k][] += dp[!now][j][k];
dp[now][k][] += dp[!now][j][k];
if (dp[now][k][] >= MOD) dp[now][k][] %= MOD;
if (dp[now][k][] >= MOD) dp[now][k][] %= MOD;
}
}
}
}
int ans = ;
for (int i = ; i <= ; ++i) {
for (int j = ; j <= ; ++j) {
ans += dp[now][i][j];
ans %= MOD;
}
}
printf("%d\n", ans);
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &L, &MOD) != EOF) work();
return ;
}
找到一个
2
4
6
9
15
25
40
64
104
169
273
441
714
这样的数列，我开始以为是f[n] = f[n - 1] + f[n - 2] + someVal
这个someVal也是固定变化的，-1、0、+1、0、-1、.....这样。
然后O（n）递推，超时，
同学说，
2 = 1 * 2
4 = 2 * 2
6 = 2 * 3
9 = 3 * 3
15 = 3 * 5
25 = 5 * 5
一路写下去，就有规律，是fib数列相乘。Orz。
然后就矩阵吧。
感觉这个，没必要卡这个吧，正解的矩阵明天再补吧，正解是很6的。（听同学的题解的）%%%
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int L, MOD;
const int maxn = ;
struct Matrix {
LL a[maxn][maxn];
int row;
int col;
};
struct Matrix matrix_mul (struct Matrix a, struct Matrix b, int MOD) { //求解矩阵a*b%MOD
struct Matrix c = {}; //这个要多次用到，栈分配问题，maxn不能开太大，
//LL的时候更加是，空间是maxn*maxn的，这样时间用得很多，4和5相差300ms
c.row = a.row; //行等于第一个矩阵的行
c.col = b.col; //列等于第二个矩阵的列
for (int i = ; i <= a.row; i++) { //枚举第一个矩阵的行
for (int j = ; j <= b.col; j++) { //枚举第二个矩阵的列，其实和上面数值一样
for (int k = ; k <= b.row; k++) { //b中的一列中，有“行”个元素 notice
c.a[i][j] += a.a[i][k] * b.a[k][j]; //这里不及时取模，又有可能错！HDU 4565
}
c.a[i][j] = (c.a[i][j] + MOD) % MOD; //如果怕出现了负数取模的话。可以这样做
}
}
return c;
}
struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) {
//求解a*b^n%MOD
while (n) {
if (n & ) {
ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律
}
n >>= ;
base = matrix_mul(base, base, MOD);
}
return ans;
}
void work() {
if (L == ) {
printf("0\n");
return;
}
if (L == ) {
printf("%d\n", % MOD);
return;
}
if (L == ) {
printf("%d\n", % MOD);
return;
}
int n = L;
Matrix t1;
t1.row = , t1.col = ;
t1.a[][] = , t1.a[][] = ;
Matrix t2;
t2.row = t2.col = ;
t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = ;
Matrix ans = quick_matrix_pow(t1, t2, n / + - , MOD);
int one = ans.a[][];
t1.row = , t1.col = ;
t1.a[][] = , t1.a[][] = ;
t2.row = t2.col = ;
t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = ;
ans = quick_matrix_pow(t1, t2, (n - ) / + - , MOD);
int two = ans.a[][];
printf("%d\n", one * two % MOD);
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &L, &MOD) != EOF) work();
return ;
}
正解是一个直接的矩阵快速幂的思路，先列出所有合法情况的后三位。
一共就6种情况。
fmm, mff, mfm, mmf, mmm, ffm，设为Fn
然后，第一个的fmm，可以由上一个的合法情况的，以fm结尾的递推过来。
所以直接加上mfm, ffm的上一个拥有的答案即可。就可以把第一个的值递推到F（n + 1）
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int L, MOD;
const int maxn = ;
struct Matrix {
LL a[maxn][maxn];
int row;
int col;
};
//应对稀疏矩阵，更快。
//struct Matrix matrix_mul(struct Matrix a, struct Matrix b, int MOD) { //求解矩阵a*b%MOD
// struct Matrix c = {0}; //这个要多次用到，栈分配问题，maxn不能开太大，
// //LL的时候更加是，空间是maxn*maxn的，这样时间用得很多，4和5相差300ms
// c.row = a.row; //行等于第一个矩阵的行
// c.col = b.col; //列等于第二个矩阵的列
// for (int i = 1; i <= a.row; ++i) {
// for (int k = 1; k <= a.col; ++k) {
// if (a.a[i][k]) { //应付稀疏矩阵，0就不用枚举下面了
// for (int j = 1; j <= b.col; ++j) {
// c.a[i][j] += a.a[i][k] * b.a[k][j];
// c.a[i][j] = (c.a[i][j] + MOD) % MOD; //负数取模
// }
// }
// }
// }
// return c;
//}
struct Matrix matrix_mul (struct Matrix a, struct Matrix b, int MOD) { //求解矩阵a*b%MOD
struct Matrix c = {}; //这个要多次用到，栈分配问题，maxn不能开太大，
//LL的时候更加是，空间是maxn*maxn的，这样时间用得很多，4和5相差300ms
c.row = a.row; //行等于第一个矩阵的行
c.col = b.col; //列等于第二个矩阵的列
for (int i = ; i <= a.row; i++) { //枚举第一个矩阵的行
for (int j = ; j <= b.col; j++) { //枚举第二个矩阵的列，其实和上面数值一样
for (int k = ; k <= b.row; k++) { //b中的一列中，有“行”个元素 notice
c.a[i][j] += a.a[i][k] * b.a[k][j]; //这里不及时取模，又有可能错！HDU 4565
}
c.a[i][j] = (c.a[i][j] + MOD) % MOD; //如果怕出现了负数取模的话。可以这样做
}
}
return c;
} struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) {
//求解a*b^n%MOD
while (n) {
if (n & ) {
ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律
}
n >>= ;
base = matrix_mul(base, base, MOD);
}
return ans;
} void work() {
int ans;
if (L == ) {
ans = ;
} else if (L == ) {
ans = % MOD;
} else if (L == ) {
ans = % MOD;
} else {
Matrix t1;
t1.row = , t1.col = ;
t1.a[][] = , t1.a[][] = , t1.a[][] = , t1.a[][] = , t1.a[][] = , t1.a[][] = ;
Matrix t2;
t2.row = t2.col = ;
t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = ;
t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = , t2.a[][] = ;
Matrix res = quick_matrix_pow(t1, t2, L - , MOD);
ans = res.a[][] + res.a[][] + res.a[][] + res.a[][] + res.a[][] + res.a[][];
}
cout << ans % MOD << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
while (cin >> L >> MOD) work();
return ;
}
找了个bug，这题可以O(L)
1、用register int
2、C++提交，时间比较快，内存比较大。而G++提交则相反。
然后O(L)可以4600ms
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int n, m;
int add[] = {-, , , };
int ans;
void work() {
if (n == ) {
printf("%d\n", % m);
return;
}
if (n == ) {
printf("%d\n", % m);
return;
}
if (n == ) {
printf("%d\n", % m);
return;
}
register int two = % m, one = % m;
register int pos = ;
for (int i = ; i <= n; ++i) {
ans = (two + one);
if (ans >= m) ans -= m;
ans = (ans + add[pos] + m);
if (ans >= m) ans %= m;
two = one;
one = ans;
pos++;
if (pos == ) pos = ;
}
printf("%d\n", ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &m) > ) work();
return ;
}
这题还可以用AC自动机 +矩阵快速幂来做
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int N = ;
struct node {
int flag;
int id;
struct node *Fail; //失败指针，匹配失败，跳去最大前后缀
struct node *pNext[N];
} tree[ * ];
int t; //字典树的节点
int getid(char ch) {
if (ch == 'f') return ;
else return ;
}
struct node *create() { //其实也只是清空数据而已，多case有用
struct node *p = &tree[t++];
p->flag = ;
p->Fail = NULL;
p->id = t - ;
for (int i = ; i < N; i++) {
p->pNext[i] = NULL;
}
return p;
}
void toinsert(struct node **T, char str[]) {
struct node *p = *T;
if (p == NULL) {
p = *T = create();
}
for (int i = ; str[i]; i++) {
int id = getid(str[i]);
if (p->pNext[id] == NULL) {
p->pNext[id] = create();
}
p = p->pNext[id];
}
p->flag++; //相同的单词算两次
return ;
}
void BuiltFail(struct node **T) {
//根节点没有失败指针,所以都是需要特判的
//思路就是去到爸爸的失败指针那里，找东西匹配，这样是最优的
struct node *p = *T; //用个p去代替修改
struct node *root = *T;
if (p == NULL) return ;
//树上bfs,要更改的是p->pNext[i]->Fail
struct node *que[t + ]; //这里的t是节点总数，字典树那里统计的，要用G++编译
int head = , tail = ;
que[tail++] = root;
while (head < tail) {
p = que[head]; //p取出第一个元素 ★
for (int i = ; i < N; i++) { //看看存不存在这个节点
if (p->pNext[i] != NULL) { //存在的才需要管失败指针。
if (p == root) { //如果爸爸是根节点的话
p->pNext[i]->Fail = root; //指向根节点
} else {
struct node *FailNode = p->Fail; //首先找到爸爸的失败指针
while (FailNode != NULL) {
if (FailNode->pNext[i] != NULL) { //存在
p->pNext[i]->Fail = FailNode->pNext[i];
if (FailNode->pNext[i]->flag) {
p->pNext[i]->flag = ;
}
break;
}
FailNode = FailNode->Fail; //回溯
}
if (FailNode == NULL) { //如果还是空，那么就指向根算了
p->pNext[i]->Fail = root;
}
}
que[tail++] = p->pNext[i]; //这个id是存在的，入队bfs
} else if (p == root) { //变化问题，使得不存在的边也建立起来。
p->pNext[i] = root;
} else {
p->pNext[i] = p->Fail->pNext[i]; //变化到LCP。可以快速匹配到病毒。
}
}
head++;
}
return ;
}
char str[];
const int maxn = + ;
struct Matrix {
LL a[maxn][maxn];
int row;
int col;
};
//应对稀疏矩阵，更快。
struct Matrix matrix_mul(struct Matrix a, struct Matrix b, int MOD) { //求解矩阵a*b%MOD
struct Matrix c = {}; //这个要多次用到，栈分配问题，maxn不能开太大，
//LL的时候更加是，空间是maxn*maxn的，这样时间用得很多，4和5相差300ms
c.row = a.row; //行等于第一个矩阵的行
c.col = b.col; //列等于第二个矩阵的列
for (int i = ; i <= a.row; ++i) {
for (int k = ; k <= a.col; ++k) {
if (a.a[i][k]) { //应付稀疏矩阵，0就不用枚举下面了
for (int j = ; j <= b.col; ++j) {
c.a[i][j] += a.a[i][k] * b.a[k][j];
c.a[i][j] = (c.a[i][j] + MOD) % MOD; //负数取模
}
}
}
}
return c;
}
struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) {
//求解a*b^n%MOD
while (n) {
if (n & ) {
ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律
}
n >>= ;
base = matrix_mul(base, base, MOD);
}
return ans;
}
int L, mod;
Matrix I, e;
void work() {
Matrix res = quick_matrix_pow(I, e, L, mod);
int ans = ;
for (int i = ; i <= t; ++i) {
ans += res.a[][i];
}
cout << ans % mod << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
t = ;
struct node *T = NULL;
toinsert(&T, "0fmf");
toinsert(&T, "0fff");
BuiltFail(&T);
t--;
I.row = I.col = t;
for (int i = ; i <= t; ++i) {
I.a[i][i] = ;
}
e.row = e.col = t;
for (int i = ; i <= t; ++i) {
if (tree[i].flag) continue;
int id1 = tree[i].id;
for (int j = ; j < N; ++j) {
if (tree[i].pNext[j]->flag) continue;
int id2 = tree[i].pNext[j]->id;
e.a[id1][id2]++;
}
}
// for (int i = 1; i <= t; ++i) {
// for (int j = 1; j <= t; ++j) {
// cout << e.a[i][j] << " ";
// }
// cout << endl;
// }
while (scanf("%d%d", &L, &mod) != EOF) work();
return ;
}
这题还可以，对询问排序，然后全部预处理出来就好，预处理的时候，同时对询问记录。Orz
这个技巧不错
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e6 + ;
struct Node {
int id, L, MOD;
bool operator < (const struct Node & rhs) const {
if (L != rhs.L) return L < rhs.L;
else return MOD < rhs.MOD;
}
}query[maxn];
int dp[][][][];
int ans[maxn];
int en = 1e6;
void work() {
int has = ;
while (scanf("%d%d", &query[has].L, &query[has].MOD) != EOF) {
query[has].id = has;
has++;
}
has--;
sort(query + , query + + has);
int toSolve = ;
while (toSolve <= has && query[toSolve].L == ) {
ans[query[toSolve].id] = % query[toSolve].MOD;
++toSolve;
}
for (int i = ; i <= ; ++i) {
dp[][][][i] = % i;
}
int now = ;
for (int i = ; i <= en; ++i) {
now = !now;
memset(dp[now], , sizeof dp[now]);
for (int j = ; j <= ; ++j) {
for (int k = ; k <= ; ++k) {
for (int res = ; res <= ; ++res) {
if (j == && k == || j == && k == ) {
dp[now][k][][res] += dp[!now][j][k][res];
if (dp[now][k][][res] >= res) dp[now][k][][res] -= res;
} else {
dp[now][k][][res] += dp[!now][j][k][res];
dp[now][k][][res] += dp[!now][j][k][res];
if (dp[now][k][][res] >= res) dp[now][k][][res] -= res;
if (dp[now][k][][res] >= res) dp[now][k][][res] -= res;
}
}
}
}
while (toSolve <= has && query[toSolve].L == i) {
int md = query[toSolve].MOD;
ans[query[toSolve].id] = (dp[now][][][md] + dp[now][][][md] + dp[now][][][md] + dp[now][][][md]) % md;
toSolve++;
}
if (toSolve > has) break;
}
for (int i = ; i <= has; ++i) {
printf("%d\n", ans[i]);
}
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
这题都我的影响实在太深了，因为我训练的时候第一个做这个题，然后不断TLE，最后放弃，但是同学们1个多小时就过了这题，（他们还过了前面的题，再做这题）然后我训练的排名掉的很厉害。
最重要的是，我找到了那个规律了，但是却做不出来。
就是那个f[n] = f[n - 1] + f[n - 2] + someVal。其实应该在超时的时候，就输出来看看有什么规律，这样还可能有机会过，我是快结束的时候，又来扛这题的。
就是不找规律，这条方程，是可以解的。
注意到他是四个一循环，就是-1、0、+1、0、......不断重复，那么，我们把
F[n] + F[n - 1] + F[n - 2] + F[n - 3]合并，那么就会使得someval变成0
F[n] + F[n - 1] + F[n - 2] + F[n - 3] =
F[n - 1] + F[n - 2] + F[n - 2] + F[n - 3] + F[n - 3] + F[n - 4] + F[n - 4] + F[n - 5]
最后得到的公式是
F[n] = F[n - 2] + F[n - 3] + 2 * F[n - 4] + F[n - 5]
这个可以矩阵快速幂
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int L, MOD;
const int maxn = ;
int ans[] = {, , , , , , };
struct Matrix {
LL a[maxn][maxn];
int row;
int col;
};
//应对稀疏矩阵，更快。
struct Matrix matrix_mul(struct Matrix a, struct Matrix b, int MOD) { //求解矩阵a*b%MOD
struct Matrix c = {}; //这个要多次用到，栈分配问题，maxn不能开太大，
//LL的时候更加是，空间是maxn*maxn的，这样时间用得很多，4和5相差300ms
c.row = a.row; //行等于第一个矩阵的行
c.col = b.col; //列等于第二个矩阵的列
for (int i = ; i <= a.row; ++i) {
for (int k = ; k <= a.col; ++k) {
if (a.a[i][k]) { //应付稀疏矩阵，0就不用枚举下面了
for (int j = ; j <= b.col; ++j) {
c.a[i][j] += a.a[i][k] * b.a[k][j];
c.a[i][j] = (c.a[i][j] + MOD) % MOD; //负数取模
}
}
}
}
return c;
}
struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) {
//求解a*b^n%MOD
while (n) {
if (n & ) {
ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律
}
n >>= ;
base = matrix_mul(base, base, MOD);
}
return ans;
} void work() {
if (L <= ) {
printf("%d\n", ans[L] % MOD);
return;
}
struct Matrix t1 = {};
t1.row = , t1.col = ;
t1.a[][] = ans[], t1.a[][] = ans[], t1.a[][] = ans[], t1.a[][] = ans[], t1.a[][] = ans[]; struct Matrix t2 = {};
t2.row = t2.col = ;
t2.a[][] = ;
t2.a[][] = t2.a[][] = ;
t2.a[][] = t2.a[][] = ;
t2.a[][] = , t2.a[][] = ;
t2.a[][] = ; struct Matrix res = quick_matrix_pow(t1, t2, L - , MOD);
printf("%d\n", res.a[][]);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &L, &MOD) != EOF) work();
return ;
}