team2012-F3-sol-0017

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：
给定一个n边形，每个顶点有两个数u和v，且 1 <= u <= p, 1 <= v <= q，并且要满足相邻的两个点至少有一个数字相同
当其中8个点的数值给定以后，求总方案数
解法：
分8段来考虑，在每一段上，设f[i]为一个4维向量表示从起点到i的方案数，其中：
f[i][0]为两个数与结尾的两个数都不同的方案数，
f[i][1]为只有第一个与结尾相同的方案数，
f[i][2]为只有第二个与结尾相同的方案数，
f[i][3]为两个都与结尾相同的方案数。

              {p+q-3, p-1, q-1, 0  }
              {1,     q-1, 0,   q-1}
那么 f[i+1] = {1,     0,   p-1, p-1} × f[i]，这样用矩阵乘法乘到结尾，然后结尾一定要取“两个都相同的”即可
              {0,     1,   1,   1  }

}}}
{{{
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

const LL MOD = 1234567890;
LL n, p, q, ans;

struct ele
{
    LL x, p, q;
}a[10];

struct mat
{
    LL dt[4][4];
    mat()
    {
        memset(dt, 0, sizeof(dt));
        for(int i=0;i<4;i++)
            dt[i][i] = 1;
    }
    mat operator*(const mat& ano)
    {
        mat ret;
        memset(&ret, 0, sizeof(ret));
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                for(int k=0;k<4;k++)
                {
                    ret.dt[i][j] += (dt[i][k] * ano.dt[k][j]) % MOD;
                    ret.dt[i][j] %= MOD;
                }
        return ret;
    }
    void operator*=(mat& ano)
    {
        (*this) = ano * (*this);
    }
}m;

void init()
{
    LL tmp[4][4] = {
        {p+q-3, p-1, q-1, 0},
        {1,     q-1, 0,   q-1},
        {1,     0,   p-1, p-1},
        {0,     1,   1,   1}
    };
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            m.dt[i][j] = tmp[i][j] % MOD;
}

void gao(int k)
{
    mat tm = m, res;
    LL pow = a[k+1].x - a[k].x;
    while(pow)
    {
        if(pow & 1)
            res *= tm;
        tm *= tm;
        pow >>= 1;
    }

    if(a[k+1].p == a[k].p && a[k+1].q == a[k].q)
        ans *= res.dt[3][3];
    else if(a[k+1].q == a[k].q)
        ans *= res.dt[3][2];
    else if(a[k+1].p == a[k].p)
        ans *= res.dt[3][1];
    else
        ans *= res.dt[3][0];
    ans %= MOD;
}

bool cmp(ele a, ele b)
{
    return a.x < b.x;
}

int main()
{
    while(~scanf("%lld %lld %lld", &n, &p, &q))
    {
        init();
        for(int i=1;i<=8;i++)
            scanf("%lld %lld %lld", &a[i].x, &a[i].p, &a[i].q);
        sort(a+1, a+8+1, cmp);
        a[9] = a[1];
        a[9].x += n;

        ans = 1;
        for(int i=1;i<=8;i++)   gao(i);
        printf("%lld\n", ans);
    }
    return 0;
}
}}}

题意：
给定一个n边形，每个顶点有两个数u和v，且 1 <= u <= p, 1 <= v <= q，并且要满足相邻的两个点至少有一个数字相同
当其中8个点的数值给定以后，求总方案数
解法：
分8段来考虑，在每一段上，设f[i]为一个4维向量表示从起点到i的方案数，其中：
f[i][0]为两个数与结尾的两个数都不同的方案数，
f[i][1]为只有第一个与结尾相同的方案数，
f[i][2]为只有第二个与结尾相同的方案数，
f[i][3]为两个都与结尾相同的方案数。
              {p+q-3, p-1, q-1, 0  }
              {1,     q-1, 0,   q-1}
那么 f[i+1] = {1,     0,   p-1, p-1} × f[i]，这样用矩阵乘法乘到结尾，然后结尾一定要取“两个都相同的”即可
              {0,     1,   1,   1  }

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const LL MOD = 1234567890;
LL n, p, q, ans;
struct ele
{
    LL x, p, q;
}a[10];
struct mat
{
    LL dt[4][4];
    mat()
    {
        memset(dt, 0, sizeof(dt));
        for(int i=0;i<4;i++)
            dt[i][i] = 1;
    }
    mat operator*(const mat& ano)
    {
        mat ret;
        memset(&ret, 0, sizeof(ret));
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                for(int k=0;k<4;k++)
                {
                    ret.dt[i][j] += (dt[i][k] * ano.dt[k][j]) % MOD;
                    ret.dt[i][j] %= MOD;
                }
        return ret;
    }
    void operator*=(mat& ano)
    {
        (*this) = ano * (*this);
    }
}m;
void init()
{
    LL tmp[4][4] = {
        {p+q-3, p-1, q-1, 0},
        {1,     q-1, 0,   q-1},
        {1,     0,   p-1, p-1},
        {0,     1,   1,   1}
    };
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            m.dt[i][j] = tmp[i][j] % MOD;
}
void gao(int k)
{
    mat tm = m, res;
    LL pow = a[k+1].x - a[k].x;
    while(pow)
    {
        if(pow & 1)
            res *= tm;
        tm *= tm;
        pow >>= 1;
    }
    if(a[k+1].p == a[k].p && a[k+1].q == a[k].q)
        ans *= res.dt[3][3];
    else if(a[k+1].q == a[k].q)
        ans *= res.dt[3][2];
    else if(a[k+1].p == a[k].p)
        ans *= res.dt[3][1];
    else
        ans *= res.dt[3][0];
    ans %= MOD;
}
bool cmp(ele a, ele b)
{
    return a.x < b.x;
}
int main()
{
    while(~scanf("%lld %lld %lld", &n, &p, &q))
    {
        init();
        for(int i=1;i<=8;i++)
            scanf("%lld %lld %lld", &a[i].x, &a[i].p, &a[i].q);
        sort(a+1, a+8+1, cmp);
        a[9] = a[1];
        a[9].x += n;
        ans = 1;
        for(int i=1;i<=8;i++)   gao(i);
        printf("%lld\n", ans);
    }
    return 0;
}