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 + 2; LL quick_pow(LL a, LL b, LL MOD) { LL base = a % MOD; LL ans = 1; while (b) { if (b & 1) { ans = (ans * base) % MOD; } base = (base * base) % MOD; b >>= 1; } return ans; } int dp[2][3][3]; //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 == 0) { printf("0 "); return; } if (L == 1) { printf("1 "); return; } // int ans = (quick_pow(2, L, MOD) + MOD - dfs(1, 0, 0)) % MOD; // printf("%d ", ans); // printf("******%d ", dfs(1, 0, 0)); memset(dp, 0, sizeof dp); dp[1][0][0] = 1; int now = 1; for (int i = 1; i <= L; ++i) { now = !now; memset(dp[now], 0, sizeof dp[now]); for (int j = 0; j <= 2; ++j) { for (int k = 0; k <= 2; ++k) { if (j == 1 && k == 2 || j == 1 && k == 1) { dp[now][k][2] += dp[!now][j][k]; if (dp[now][k][2] >= MOD) dp[now][k][2] %= MOD; } else { dp[now][k][1] += dp[!now][j][k]; dp[now][k][2] += dp[!now][j][k]; if (dp[now][k][1] >= MOD) dp[now][k][1] %= MOD; if (dp[now][k][2] >= MOD) dp[now][k][2] %= MOD; } } } } int ans = 0; for (int i = 1; i <= 2; ++i) { for (int j = 1; j <= 2; ++j) { ans += dp[now][i][j]; ans %= MOD; } } printf("%d ", 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 0; }
找到一个
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 = 4; 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 j = 1; j <= b.col; j++) { //枚举第二个矩阵的列，其实和上面数值一样 for (int k = 1; 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 & 1) { ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律 } n >>= 1; base = matrix_mul(base, base, MOD); } return ans; } void work() { if (L == 0) { printf("0 "); return; } if (L == 1) { printf("%d ", 2 % MOD); return; } if (L == 2) { printf("%d ", 4 % MOD); return; } int n = L; Matrix t1; t1.row = 1, t1.col = 2; t1.a[1][1] = 2, t1.a[1][2] = 1; Matrix t2; t2.row = t2.col = 2; t2.a[1][1] = 1, t2.a[1][2] = 1; t2.a[2][1] = 1, t2.a[2][2] = 0; Matrix ans = quick_matrix_pow(t1, t2, n / 2 + 1 - 2, MOD); int one = ans.a[1][1]; t1.row = 1, t1.col = 2; t1.a[1][1] = 2, t1.a[1][2] = 1; t2.row = t2.col = 2; t2.a[1][1] = 1, t2.a[1][2] = 1; t2.a[2][1] = 1, t2.a[2][2] = 0; ans = quick_matrix_pow(t1, t2, (n - 1) / 2 + 2 - 2, MOD); int two = ans.a[1][1]; printf("%d ", 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 0; }
正解是一个直接的矩阵快速幂的思路，先列出所有合法情况的后三位。
一共就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 = 7; 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 = {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 j = 1; j <= b.col; j++) { //枚举第二个矩阵的列，其实和上面数值一样 for (int k = 1; 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 & 1) { ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律 } n >>= 1; base = matrix_mul(base, base, MOD); } return ans; } void work() { int ans; if (L == 0) { ans = 0; } else if (L == 1) { ans = 2 % MOD; } else if (L == 2) { ans = 4 % MOD; } else { Matrix t1; t1.row = 1, t1.col = 6; t1.a[1][1] = 1, t1.a[1][2] = 1, t1.a[1][3] = 1, t1.a[1][4] = 1, t1.a[1][5] = 1, t1.a[1][6] = 1; Matrix t2; t2.row = t2.col = 6; t2.a[1][1] = 0, t2.a[1][2] = 0, t2.a[1][3] = 0, t2.a[1][4] = 1, t2.a[1][5] = 1, t2.a[1][6] = 0; t2.a[2][1] = 0, t2.a[2][2] = 0, t2.a[2][3] = 0, t2.a[2][4] = 0, t2.a[2][5] = 0, t2.a[2][6] = 1; t2.a[3][1] = 1, t2.a[3][2] = 0, t2.a[3][3] = 0, t2.a[3][4] = 0, t2.a[3][5] = 0, t2.a[3][6] = 0; t2.a[4][1] = 0, t2.a[4][2] = 1, t2.a[4][3] = 1, t2.a[4][4] = 0, t2.a[4][5] = 0, t2.a[4][6] = 0; t2.a[5][1] = 0, t2.a[5][2] = 0, t2.a[5][3] = 0, t2.a[5][4] = 1, t2.a[5][5] = 1, t2.a[5][6] = 0; t2.a[6][1] = 1, t2.a[6][2] = 0, t2.a[6][3] = 0, t2.a[6][4] = 0, t2.a[6][5] = 0, t2.a[6][6] = 0; Matrix res = quick_matrix_pow(t1, t2, L - 3, MOD); ans = res.a[1][1] + res.a[1][2] + res.a[1][3] + res.a[1][4] + res.a[1][5] + res.a[1][6]; } 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 0; }
找了个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[] = {-1, 0, 1, 0}; int ans; void work() { if (n == 1) { printf("%d ", 2 % m); return; } if (n == 2) { printf("%d ", 4 % m); return; } if (n == 3) { printf("%d ", 6 % m); return; } register int two = 4 % m, one = 6 % m; register int pos = 0; for (int i = 4; 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 == 4) pos = 0; } printf("%d ", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &n, &m) > 0) work(); return 0; }
这题还可以用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 = 2; struct node { int flag; int id; struct node *Fail; //失败指针，匹配失败，跳去最大前后缀 struct node *pNext[N]; } tree[10 * 20]; int t; //字典树的节点 int getid(char ch) { if (ch == 'f') return 0; else return 1; } struct node *create() { //其实也只是清空数据而已，多case有用 struct node *p = &tree[t++]; p->flag = 0; p->Fail = NULL; p->id = t - 1; for (int i = 0; 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 = 1; 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 + 20]; //这里的t是节点总数，字典树那里统计的，要用G++编译 int head = 0, tail = 0; que[tail++] = root; while (head < tail) { p = que[head]; //p取出第一个元素 ★ for (int i = 0; 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 = 1; } 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[222]; const int maxn = 6 + 3; 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 quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) { //求解a*b^n%MOD while (n) { if (n & 1) { ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律 } n >>= 1; 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 = 0; for (int i = 1; i <= t; ++i) { ans += res.a[1][i]; } cout << ans % mod << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif t = 1; struct node *T = NULL; toinsert(&T, "0fmf"); toinsert(&T, "0fff"); BuiltFail(&T); t--; I.row = I.col = t; for (int i = 1; i <= t; ++i) { I.a[i][i] = 1; } e.row = e.col = t; for (int i = 1; i <= t; ++i) { if (tree[i].flag) continue; int id1 = tree[i].id; for (int j = 0; 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 0; }
这题还可以，对询问排序，然后全部预处理出来就好，预处理的时候，同时对询问记录。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 + 20; 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[2][3][3][32]; int ans[maxn]; int en = 1e6; void work() { int has = 1; while (scanf("%d%d", &query[has].L, &query[has].MOD) != EOF) { query[has].id = has; has++; } has--; sort(query + 1, query + 1 + has); int toSolve = 1; while (toSolve <= has && query[toSolve].L == 1) { ans[query[toSolve].id] = 2 % query[toSolve].MOD; ++toSolve; } for (int i = 1; i <= 30; ++i) { dp[0][0][0][i] = 1 % i; } int now = 0; for (int i = 1; i <= en; ++i) { now = !now; memset(dp[now], 0, sizeof dp[now]); for (int j = 0; j <= 2; ++j) { for (int k = 0; k <= 2; ++k) { for (int res = 1; res <= 30; ++res) { if (j == 1 && k == 1 || j == 1 && k == 2) { dp[now][k][2][res] += dp[!now][j][k][res]; if (dp[now][k][2][res] >= res) dp[now][k][2][res] -= res; } else { dp[now][k][1][res] += dp[!now][j][k][res]; dp[now][k][2][res] += dp[!now][j][k][res]; if (dp[now][k][1][res] >= res) dp[now][k][1][res] -= res; if (dp[now][k][2][res] >= res) dp[now][k][2][res] -= res; } } } } while (toSolve <= has && query[toSolve].L == i) { int md = query[toSolve].MOD; ans[query[toSolve].id] = (dp[now][1][1][md] + dp[now][1][2][md] + dp[now][2][1][md] + dp[now][2][2][md]) % md; toSolve++; } if (toSolve > has) break; } for (int i = 1; i <= has; ++i) { printf("%d ", ans[i]); } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
这题都我的影响实在太深了，因为我训练的时候第一个做这个题，然后不断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 = 8; int ans[] = {0, 2, 4, 6, 9, 15, 25}; 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 quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) { //求解a*b^n%MOD while (n) { if (n & 1) { ans = matrix_mul(ans, base, MOD);//传数组不能乱传,不满足交换律 } n >>= 1; base = matrix_mul(base, base, MOD); } return ans; } void work() { if (L <= 6) { printf("%d ", ans[L] % MOD); return; } struct Matrix t1 = {0}; t1.row = 1, t1.col = 5; t1.a[1][1] = ans[5], t1.a[1][2] = ans[4], t1.a[1][3] = ans[3], t1.a[1][4] = ans[2], t1.a[1][5] = ans[1]; struct Matrix t2 = {0}; t2.row = t2.col = 5; t2.a[1][2] = 1; t2.a[2][1] = t2.a[2][3] = 1; t2.a[3][1] = t2.a[3][4] = 1; t2.a[4][1] = 2, t2.a[4][5] = 1; t2.a[5][1] = 1; struct Matrix res = quick_matrix_pow(t1, t2, L - 5, MOD); printf("%d ", res.a[1][1]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &L, &MOD) != EOF) work(); return 0; }