[CQOI2018]交错序列

嘟嘟嘟

要是求交错序列的个数和就好了，那我一秒就能切。

换成这个，我就不会了。

我一直想枚举1的个数，然后算出在长度为\(n\)的序列里，有多少个合法的序列，然后又觉得这好像是什么插板法，但是每一个盒子里必须有球，还不会。查了一下发现这东西\(O(1)\)还求不了，于是彻底放弃了。

正解是这样的，首先还得稍微推一下式子。

\[x ^ a y ^ b = (n - y) ^ a y ^ b
\]

然后利用二项式定理

\[(n - y) ^ a y ^ b = \sum _ {i = 0} ^ a C_{a} ^ {i} n ^ i (-1) ^ {a - i} y ^ {a + b - i}
\]

于是我们发现，只用求\(y\)的和的\(x\)次幂就行了。

怎么求咧，这时候就要用dp了。

令\(dp[i][j][0 / 1]\)表示长度为\(i\)的序列中，这一位填0 / 1时1的个数的\(j\)次幂。那么分情况转移：

当这一位填0时，1的个数不变，则\(dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1]\)。

当这一位填1时，考虑\(y\)加了1，则\((y + 1) ^ j = \sum _ {k = 0} ^ {j} C_{j} ^ {k} y ^ j\)，于是有\(dp[i][j][1] = \sum _ {k = 0} ^ {j} C_{j} ^ {k} dp[i - 1][j][0]\)

讲真这时候维护前缀和\(O(n)\)dp应该已经能过了，但是交上去就是TLE，所以只能改成矩乘了（还得卡常）。

矩阵是一个边长为\(2(a + b)\)的正方形矩阵，用样例一构造后的矩阵张这个样子：

1 0 0 0 1 0 0 0

0 1 0 0 0 1 0 0

0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1

1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 2 1 0 0 0 0 0

1 3 3 1 0 0 0 0

总结一下，感觉上点难度的dp题有一部分就是在dp之前先要推一推式子，推到觉得可以dp的时候再开始dp。至于啥时候觉得可以dp，估计这就得靠刷题吧……

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 205;

inline ll read()

{

    ll ans = 0;

    char ch = getchar(), last = ' ';

    while(!isdigit(ch)) last = ch, ch = getchar();

    while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

    if(last == '-') ans = -ans;

    return ans;

}

inline void write(ll x)

{

    if(x < 0) x = -x, putchar('-');

    if(x >= 10) write(x / 10);

    putchar(x % 10 + '0');

}

int n, a, b, mod, Max;

struct Mat

{

    ll a[maxn][maxn];

    In Mat operator * (const Mat& oth)const

    {

        static Mat ret; Mem(ret.a, 0);

        for(int i = 0; i <= Max; ++i)

            for(int j = 0; j <= Max; ++j)

            {

                for(int k = 0; k <= Max; ++k) ret.a[i][j] += a[i][k] * oth.a[k][j];

                ret.a[i][j] %= mod;

            }

        return ret;

    }

}f;

ll C[maxn][maxn];

In void init()

{

    for(int i = 0; i <= a + b; ++i) C[i][0] = 1;

    for(int i = 1; i <= a + b; ++i)

        for(int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;

    Mem(f.a, 0); Max = ((a + b) << 1) + 1;

    for(int i = 0; i <= a + b; ++i) f.a[i][i] = f.a[i][a + b + 1 + i] = 1;

    for(int i = 0; i <= a + b; ++i)

        for(int j = 0; j <= i; ++j) f.a[a + b + 1 + i][j] = C[i][j];

}

In Mat quickpow(Mat A, ll b)

{

    Mat ret; Mem(ret.a, 0);

    for(int i = 0; i <= Max; ++i) ret.a[i][i] = 1;

    for(; b; b >>= 1, A = A * A)

        if(b & 1) ret = ret * A;

    return ret;

}

ll ans[maxn];

int main()

{

    n = read(), a = read(), b = read(), mod = read();

    init();

    Mat A = quickpow(f, n);

    for(int i = 0; i <= a; ++i)

    {

        for(int j = 0; j <= Max; ++j) ans[i] += A.a[i][j];

        for(int j = 0; j <= Max; ++j) ans[i] += A.a[a + b + 1 + i][j];

        ans[i] %= mod;

    }

    ll Ans = 0, tp = 1;

    for(int i = 0, flg = pow(-1, a); i <= a; ++i, tp = tp * n % mod, flg *= (-1))

        Ans = (Ans + C[a][i] * tp % mod * (A.a[a + b - i][0] + A.a[a + b - i + a + b + 1][0]) * flg % mod + mod) % mod;

    write(Ans), enter;

    return 0;

}

秒客网

[CQOI2018]交错序列

相关文章