team2012-E1-mysol-0017

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

给出一个 N 边形，其中每个顶点都有两个值 U[i] 和 V[i]
且满足 1 <= U[i] <= P，1 <= V[i] <= Q，相邻的两个顶点至少有一个值相同
再给出八个已知条件，表示第 X[i] 个点的值一定是 U[X[i]] 和 V[X[i]]
求在这种限制条件下，不同的 U[i] 和 V[i] 组合的方案数

如果没有限制条件，很明显就是简单的公式题
有了限制条件之后，只能考虑用矩阵做递推，现在考虑 X[i] 至 X[i + 1] 区间
令每个向量 a[p] 有四个元素，表示在位置 p 的方案数，四个元素分别是
0: U 的值和 U[X[i + 1]] 不同，V 的值和 V[X[i + 1]] 不同的方案数
1: U 的值和 U[X[i + 1]] 不同，V 的值和 V[X[i + 1]] 相同的方案数
2: U 的值和 U[X[i + 1]] 相同，V 的值和 V[X[i + 1]] 不同的方案数
3: U 的值和 U[X[i + 1]] 相同，V 的值和 V[X[i + 1]] 相同的方案数

转移矩阵是 4 * 4 的，根据所列的向量 a 的四个元素的意义进行转移
那 16 个值写起来比较麻烦就省略了，大家可以参考代码里写的值，去推一推

总之，有了初始向量和转移矩阵后，直接矩阵快速幂就搞定了
当时验题时我写的是 9 * 9 的转移矩阵，验到早上 9 点才验出来...

// By 猛犸也钻地 @ 2012.07.22 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

class MatInt{
public:
    static const int MOD = 1234567890;
    typedef long long LL;
    typedef vector<int> BAR;
    int n,m;
    vector<BAR> u;
    MatInt():n(),m(){}
    MatInt(int c):u(c,BAR(c)){for(n=m=c;c--;u[c][c]=1);}
    MatInt(int n, int m):n(n),m(m),u(n,BAR(m)){}
    BAR& operator [](int idx){return u[idx];}
    const BAR& operator [](int idx) const{return u[idx];}
    operator bool() const{return n && m;}
    MatInt operator ~() const{
        MatInt ret(m,n);
        for(int i=0;i<m;i++) for(int j=0;j<n;j++) ret[i][j]=u[j][i];
        return ret;
    }
    MatInt operator *(const MatInt& c) const{
        if(m!=c.n) return MatInt();
        MatInt ret(n,c.m),v=~c;
        for(int i=0;i<n;i++) for(int j=0;j<c.m;j++) for(int k=0;k<m;k++)
            ret[i][j]=(ret[i][j]+LL(u[i][k])*v[j][k])%MOD;
        return ret;
    }
    MatInt& operator *=(const MatInt& c){return *this=*this*c;}
    MatInt pow(long long e) const{
        if(n!=m) return MatInt();
        MatInt ret=n,c=*this;
        for(;e;e>>=1,c*=c) if(e&1) ret*=c;
        return ret;
    }
};

int main(){
    long long n,p,q,x[9],u[9],v[9];
    while(scanf("%lld%lld%lld",&n,&p,&q)==3){
        int m=8,ans=1;
        for(int i=0;i<m;i++){
            scanf("%lld%lld%lld",x+i,u+i,v+i);
            for(int j=0;j<i;j++) if(x[i]<x[j]){
                swap(x[i],x[j]);
                swap(u[i],u[j]);
                swap(v[i],v[j]);
            }
        }
        x[m]=x[0]+n,u[m]=u[0],v[m]=v[0];
        for(int i=0;i<m;i++){
            MatInt a(1,4),e(4,4);
            const long long r[4][4]={
                {p+q-3, 1 , 1 ,0},
                { q-1 ,p-1, 0 ,1},
                { p-1 , 0 ,q-1,1},
                {  0  ,p-1,q-1,1},
            };
            for(int j=0;j<4;j++) for(int k=0;k<4;k++)
                e[j][k]=r[j][k]%e.MOD;
            a[0][(u[i]==u[i+1])*2|(v[i]==v[i+1])]=ans;
            a*=e.pow(x[i+1]-x[i]);
            ans=a[0][3];
        }
        printf("%d\n",ans);
    }
}
}}}

/* 解题报告 //
给出一个 N 边形，其中每个顶点都有两个值 U[i] 和 V[i]
且满足 1 <= U[i] <= P，1 <= V[i] <= Q，相邻的两个顶点至少有一个值相同
再给出八个已知条件，表示第 X[i] 个点的值一定是 U[X[i]] 和 V[X[i]]
求在这种限制条件下，不同的 U[i] 和 V[i] 组合的方案数
如果没有限制条件，很明显就是简单的公式题
有了限制条件之后，只能考虑用矩阵做递推，现在考虑 X[i] 至 X[i + 1] 区间
令每个向量 a[p] 有四个元素，表示在位置 p 的方案数，四个元素分别是
0: U 的值和 U[X[i + 1]] 不同，V 的值和 V[X[i + 1]] 不同的方案数
1: U 的值和 U[X[i + 1]] 不同，V 的值和 V[X[i + 1]] 相同的方案数
2: U 的值和 U[X[i + 1]] 相同，V 的值和 V[X[i + 1]] 不同的方案数
3: U 的值和 U[X[i + 1]] 相同，V 的值和 V[X[i + 1]] 相同的方案数
转移矩阵是 4 * 4 的，根据所列的向量 a 的四个元素的意义进行转移
那 16 个值写起来比较麻烦就省略了，大家可以参考代码里写的值，去推一推
总之，有了初始向量和转移矩阵后，直接矩阵快速幂就搞定了
当时验题时我写的是 9 * 9 的转移矩阵，验到早上 9 点才验出来...
// By 猛犸也钻地 @ 2012.07.22 */

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class MatInt{
public:
    static const int MOD = 1234567890;
    typedef long long LL;
    typedef vector<int> BAR;
    int n,m;
    vector<BAR> u;
    MatInt():n(),m(){}
    MatInt(int c):u(c,BAR(c)){for(n=m=c;c--;u[c][c]=1);}
    MatInt(int n, int m):n(n),m(m),u(n,BAR(m)){}
    BAR& operator [](int idx){return u[idx];}
    const BAR& operator [](int idx) const{return u[idx];}
    operator bool() const{return n && m;}
    MatInt operator ~() const{
        MatInt ret(m,n);
        for(int i=0;i<m;i++) for(int j=0;j<n;j++) ret[i][j]=u[j][i];
        return ret;
    }
    MatInt operator *(const MatInt& c) const{
        if(m!=c.n) return MatInt();
        MatInt ret(n,c.m),v=~c;
        for(int i=0;i<n;i++) for(int j=0;j<c.m;j++) for(int k=0;k<m;k++)
            ret[i][j]=(ret[i][j]+LL(u[i][k])*v[j][k])%MOD;
        return ret;
    }
    MatInt& operator *=(const MatInt& c){return *this=*this*c;}
    MatInt pow(long long e) const{
        if(n!=m) return MatInt();
        MatInt ret=n,c=*this;
        for(;e;e>>=1,c*=c) if(e&1) ret*=c;
        return ret;
    }
};
int main(){
    long long n,p,q,x[9],u[9],v[9];
    while(scanf("%lld%lld%lld",&n,&p,&q)==3){
        int m=8,ans=1;
        for(int i=0;i<m;i++){
            scanf("%lld%lld%lld",x+i,u+i,v+i);
            for(int j=0;j<i;j++) if(x[i]<x[j]){
                swap(x[i],x[j]);
                swap(u[i],u[j]);
                swap(v[i],v[j]);
            }
        }
        x[m]=x[0]+n,u[m]=u[0],v[m]=v[0];
        for(int i=0;i<m;i++){
            MatInt a(1,4),e(4,4);
            const long long r[4][4]={
                {p+q-3, 1 , 1 ,0},
                { q-1 ,p-1, 0 ,1},
                { p-1 , 0 ,q-1,1},
                {  0  ,p-1,q-1,1},
            };
            for(int j=0;j<4;j++) for(int k=0;k<4;k++)
                e[j][k]=r[j][k]%e.MOD;
            a[0][(u[i]==u[i+1])*2|(v[i]==v[i+1])]=ans;
            a*=e.pow(x[i+1]-x[i]);
            ans=a[0][3];
        }
        printf("%d\n",ans);
    }
}