@2368860385 2018-08-31T08:30:13.000000Z 字数 4207 阅读 182

五校联考day1——2018.8.26

比赛总结

预计：100 + 100 + 10
实际：100 + 50 + 10

考试总结：

开始先看了一共半小时。想出了T1,T2，T3用容斥推出了小样例，所以一直感觉T3就是容斥。
T1：模拟题。写的时候封装几个函数，可以好写些。

T2：开始感觉是陌上花开，于是想CDQ分治，（CDQ好像忘了怎么写了。。）想着想着发现是二维偏序，然后用树状数组直接求就好了。直接求前面有多少个数比它小，后面多少个数比他大。
感觉会爆int，改成了longlong。
怕中间会爆int，中间的乘法加上1ll。
之后造了一组数据检验，n=200000,a[]=1,2,3...
然后找一下规律，推一下结论，就用一个O(n)的程序跑出答案，在用写的程序跑，发现答案一样。于是就写T3了。
最后要取模，模1e9+7。。。于是没了50分。

T3：写完T2，然后来看T3，继续用容斥推。
先求出上面的环合法的方案数，为x，然后x*x就是总的。然后减去上下可能有相同的方案数。减去有一个相同的，加上两个相同，减去三个相同。那么现在又k个相同的，然后剩下的n-k个的颜色要求满足下面的环合法的方案数，然后这里求不出了。
n=4的情况就不能直接算出了，然后想了很长时间如何求，发现不能直接求。最后写了n=3的情况，n=4的讨论的太多，来不及写了。还有m=2的情况。

题解
T1：模拟
T2：树状数组，查前面有多少个数比它小，后面多少个数比他大。
T3：

将上面的环拆开，下面的拆开，再增加一个点n+1，现在就是给这个图染色，要求相邻三个点颜色不同，n+1和1相同。
枚举到每一行，右上的点的颜色一定不会和相邻的相同，它的状态只会和

左上角是第一行第一列，左下是第二行第一列，右上是第一行第i列，右下是第二行第i列
f[i][0/1/2][0/1/2] 表示当前填到第 i 列，右上角的点颜色和左上角左下
角都不同/和左上角相同/左下角相同，右下角的点颜色和左上角左下角
都不同/和左上角相同/左下角相同的方案数。

O(N)递推

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 1000100; 
const LL mod = 1e9 + 7;
LL f[N][3][3];
int main() {
    LL n,m; cin >> n >> m;
    if (m == 2) {
        if (n & 1) cout << 0;
        else cout << 2;
        return 0;
    }
    LL m23 = 1ll * (m - 2) * (m - 3) % mod;
    LL m33 = 1ll * (m - 3) * (m - 3) % mod;
    LL m43 = 1ll * ((m - 4) * (m - 4) + (m - 3)) % mod;
    LL m2 = 1ll * (m - 2) % mod;
    LL m3 = 1ll * (m - 3) % mod;
    f[1][1][2] = 1ll * m * (m - 1) % mod;
    for (int i=2; i<=n+1; ++i) {
        f[i][0][0] = (  
            (f[i-1][1][2] + f[i-1][2][1]) * m23 % mod + 
            (f[i-1][1][0] + f[i-1][0][1] + f[i-1][2][0] + f[i-1][0][2]) * m33 % mod + 
            (f[i-1][0][0]) * m43 % mod
        ) % mod;
        f[i][0][1] = (
            (f[i-1][0][0] + f[i-1][0][2]) * m3 % mod + 
            (f[i-1][1][0] + f[i-1][1][2] + f[i-1][2][0]) * m2 % mod
        ) % mod;
        f[i][1][0] = (
            (f[i-1][0][0] + f[i-1][2][0]) * m3 % mod + 
            (f[i-1][0][1] + f[i-1][2][1] + f[i-1][0][2]) * m2 % mod 
        ) % mod;
        f[i][0][2] = (
            (f[i-1][0][0] + f[i-1][0][1]) * m3 % mod + 
            (f[i-1][2][0] + f[i-1][2][1] + f[i-1][1][0]) * m2 % mod
        ) % mod;
        f[i][2][0] = (
            (f[i-1][0][0] + f[i-1][1][0]) * m3 % mod + 
            (f[i-1][0][2] + f[i-1][1][2] + f[i-1][0][1]) * m2 % mod
        ) % mod;
        f[i][1][2] = (
            f[i-1][0][0] + f[i-1][0][1] + f[i-1][2][0] + f[i-1][2][1]
        ) % mod;
        f[i][2][1] = (
            f[i-1][0][0] + f[i-1][0][2] + f[i-1][1][0] + f[i-1][1][2]
        ) % mod;
    }
    LL ans = (f[n+1][1][2]) % mod;
    cout << ans;
    return 0;
}

然后加上矩阵快速幂优化。
根据上面的转移方程推出矩阵。
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ B_{i-1} \ \ \ \ \ \ \ \ \ \ \ \ = \ \ \ \ \ \ \ \ \ \ \ \ \ C_{i}$
${\left[ \begin{matrix} m_{43} & m_{33} & m_{33} &m_{33} &m_{23} & m_{33} &m_{23} \\ m_3 & 0 & m_3 & m_2 & m_2& m_2 & 0 \\ m_3 & m_3 &0 & m_2 & 0& m_2 & m_2 \\ m_3 & m_2 & m_2 &0 & 0& m_3 & m_2 \\ 1 & 1 & 0& 0& 0& 1 & 1\\ m_3 & m_2 & m_2 & m_3 & m_2 & 0&0 \\ 1 &0 & 1 & 1 & 1 & 0 & 0 \end{matrix} \right] } \times { \left[ \begin{matrix} & f[i-1][0][0] & \\ & f[i-1][0][1] & \\ & f[i-1][0][2] & \\ & f[i-1][1][0] &\\ & f[i-1][1][2] & \\ & f[i-1][2][0] & \\ & f[i-1][2][1] & \end{matrix} \right] }= { \begin{bmatrix} & f[i][0][0] & \\ & f[i][0][1] & \\ & f[i][0][2] & \\ & f[i][1][0] &\\ & f[i][1][2] & \\ & f[i][2][0] & \\ & f[i][2][1] & \end{bmatrix} }$

$A \times B_1 = C_2$
$A \times B_2 = C_3$ 因为 $B_2 = C_2$ 所以： $A \times A \times B_1 = C_3$
同理可知 $A^3 \times B_1 = C_4$
$...$
$A^n \times B_1 = C_{n+1}$
因为A矩阵的大小是 $7 \times 7$ 的，然后快速幂只进行 $log_2n$ 次矩阵乘法，所以复杂度是 $O(log_2n \times 7^3)$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const int N = 7;
struct Matrix{
    LL a[N][N];
    void init() {
        for (int i=0; i<N; ++i) a[i][i] = 1;
    }
    void Clear() {
        memset(a, 0, sizeof(a));
    }
};
Matrix mul(Matrix A, Matrix B) {
    Matrix C;
    C.Clear();
    for (int k=0; k<N; ++k) 
        for (int i=0; i<N; ++i) 
            for (int j=0; j<N; ++j) 
                C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j]) % mod;
    return C;
}
Matrix ksm(Matrix a,LL b) {
    Matrix ans;
    ans.Clear();
    ans.init();
    while (b) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}
int main() {
    LL n,m; cin >> n >> m;
    if (m == 2) {
        if (n & 1) cout << 0;
        else cout << 2;
        return 0;
    }
    LL m23 = 1ll * (m - 2) * (m - 3) % mod;
    LL m33 = 1ll * (m - 3) * (m - 3) % mod;
    LL m43 = 1ll * ((m - 4) * (m - 4) + (m - 3)) % mod;
    LL m2 = 1ll * (m - 2) % mod;
    LL m3 = 1ll * (m - 3) % mod;
    Matrix A; A.Clear(); //--清空A！！！
    if (m >= 4) A.a[0][0] = m43;
    A.a[0][1] = A.a[0][2] = A.a[0][3] = A.a[0][5] = m33;
    A.a[0][4] = A.a[0][6] = m23;
    A.a[1][0] = A.a[1][2] = A.a[2][0] = A.a[2][1] = A.a[3][0] = A.a[3][5] = A.a[5][0] = A.a[5][3] = m3;
    A.a[1][3] = A.a[1][4] = A.a[1][5] = A.a[2][3] = A.a[2][5] = A.a[2][6] = 
    A.a[3][1] = A.a[3][2] = A.a[3][6] = A.a[5][1] = A.a[5][2] = A.a[5][4] = m2;
    A.a[4][0] = A.a[4][1] = A.a[4][5] = A.a[4][6] = A.a[6][0] = A.a[6][2] = A.a[6][3] = A.a[6][4] = 1;
    A = ksm(A, n);
    LL ans = A.a[4][4] * m % mod * (m - 1) % mod;
    cout << ans;
    return 0;
}

五校联考day1——2018.8.26

考试总结：

内容目录