首页 > 代码库 > hdu 2604 Queuing dp找规律 然后矩阵快速幂。坑！！

hdu 2604 Queuing dp找规律 然后矩阵快速幂。坑！！

2024-09-06 04:51:48   223人阅读

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\n");
        return;
    }
    if (L == 1) {
        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, 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\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 0;
}
View Code

找到一个

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\n");
        return;
    }
    if (L == 1) {
        printf("%d\n", 2 % MOD);
        return;
    }
    if (L == 2) {
        printf("%d\n", 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\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 0;
}
View Code

 

hdu 2604 Queuing dp找规律 然后矩阵快速幂。坑！！


联系
我们