prow2012-A3-0017

从 Trac 迁移的文章

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

原文章内容如下：

题意是说，一个正多边形有N个点，每个点有2个属性值（1..P，1..Q），相邻两个点必须有一种属性相同。

给出8个点的属性，求样的正多边形数量。 

首先写出DP方程，f[i,0,0]表示到第i个，跟末尾的参照两个属性都不相同的方案数，f[i,0,1]表示第二个属性相同,f[i,1,0],f[i,1,1]依次类推。

转移的方法就是右乘上这个矩阵：
{{{
    ULL mm[6][6] = {
        {(P+Q-3)%MOD,1,1,0},
        {(Q-1)%MOD,(P-1)%MOD,0,1},
        {(P-1)%MOD,0,(Q-1)%MOD,1},
        {0,(P-1)%MOD,(Q-1)%MOD,1},
    };
}}}

注意所有数字都要long long，WA过；注意输入的位置可能相同，需要特判，WA过。




{{{

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
typedef   unsigned long long ULL;

struct Mat {
   ULL M[6][6];

    void clear() {
        memset(M, 0, sizeof (M));
    }
};
int N, M, K;
int MOD = 1234567890;

void copy(Mat &A, Mat &B) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A.M[i][j] = B.M[i][j];
}

void Mmut(Mat &A, Mat &B) {
    Mat C;
    int i, j, k;
    C.clear();
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (A.M[i][j]) {
                for (k = 0; k < N; k++)
                {
                    C.M[i][k] += A.M[i][j] * B.M[j][k];
                    C.M[i][k]%=MOD;
                }
            }
    copy(A, C);
}
ULL pos[10],p[10],q[10];
int order[10];
bool cmp(int i,int j){
    return pos[i]<pos[j];
}
int main(){

    N = 4;
    ULL L,P,Q;
    long long len;
    int i,j,k;  
    while(cin>>L>>P>>Q){
    ULL mm[6][6] = {
        {(P+Q-3)%MOD,1,1,0},
        {(Q-1)%MOD,(P-1)%MOD,0,1},
        {(P-1)%MOD,0,(Q-1)%MOD,1},
        {0,(P-1)%MOD,(Q-1)%MOD,1},
    };
    if (P+Q-3<0) mm[0][0] = 0;
    Mat stand;
    stand.clear();
    memcpy(stand.M,mm,sizeof(mm));
        for (i=0;i<8;i++){
            cin>>pos[i]>>p[i]>>q[i];

            pos[i]--;
            order[i] = i;
        }
        sort(order,order+8,cmp);
        ULL ans = 1;
        for (i=0;i<8;i++){
            if (i==7) len = (pos[order[0]]+L-pos[order[i]])%L-1;
            else len = (pos[order[i+1]]-pos[order[i]])-1;
            if (len==-1){
                if (p[order[i]]!=p[order[(i+1)%8]]||
                    q[order[i]]!=q[order[(i+1)%8]])
                {
                    ans = 0;
                    break;
                }else continue;
            }
            Mat R,res;
            R.clear(),res.clear();
            for (j=0;j<N;j++)
                res.M[j][j] = 1;
            copy(R,stand);
            while(len){
                if (len&1) Mmut(res,R);
                Mmut(R,R);
                len>>=1;
            }

            Mat init;
            init.clear();
            bool a = (p[order[i]]==p[(order[(i+1)%8])]);
            bool b = (q[order[i]]==q[(order[(i+1)%8])]);


            if (a&&b) init.M[0][3] = 1;
            else  if (b) init.M[0][1] = 1;
            else  if (a) init.M[0][2] = 1;
            else init.M[0][0] = 1;

            Mmut(init,res);
            ULL tmp = init.M[0][1]+init.M[0][2]+init.M[0][3];
            tmp%=MOD;
            ans*=tmp;
            ans%=MOD;
            //cout<<init.M[0][1]+init.M[0][2]+init.M[0][3]<<" "<<i<<endl;
        }
        cout<<ans<<endl;
    }
}







}}}

题意是说，一个正多边形有N个点，每个点有2个属性值（1..P，1..Q），相邻两个点必须有一种属性相同。

给出8个点的属性，求样的正多边形数量。

首先写出DP方程，f[i,0,0]表示到第i个，跟末尾的参照两个属性都不相同的方案数，f[i,0,1]表示第二个属性相同,f[i,1,0],f[i,1,1]依次类推。

转移的方法就是右乘上这个矩阵：

   ULL mm[6][6] = {
        {(P+Q-3)%MOD,1,1,0},
        {(Q-1)%MOD,(P-1)%MOD,0,1},
        {(P-1)%MOD,0,(Q-1)%MOD,1},
        {0,(P-1)%MOD,(Q-1)%MOD,1},
    };

注意所有数字都要long long，WA过；注意输入的位置可能相同，需要特判，WA过。

#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <math.h>
using namespace std;
typedef   unsigned long long ULL;
struct Mat {
   ULL M[6][6];
    void clear() {
        memset(M, 0, sizeof (M));
    }
};
int N, M, K;
int MOD = 1234567890;
void copy(Mat &A, Mat &B) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A.M[i][j] = B.M[i][j];
}
void Mmut(Mat &A, Mat &B) {
    Mat C;
    int i, j, k;
    C.clear();
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (A.M[i][j]) {
                for (k = 0; k < N; k++)
                {
                    C.M[i][k] += A.M[i][j] * B.M[j][k];
                    C.M[i][k]%=MOD;
                }
            }
    copy(A, C);
}
ULL pos[10],p[10],q[10];
int order[10];
bool cmp(int i,int j){
    return pos[i]<pos[j];
}
int main(){
    N = 4;
    ULL L,P,Q;
    long long len;
    int i,j,k;  
    while(cin>>L>>P>>Q){
    ULL mm[6][6] = {
        {(P+Q-3)%MOD,1,1,0},
        {(Q-1)%MOD,(P-1)%MOD,0,1},
        {(P-1)%MOD,0,(Q-1)%MOD,1},
        {0,(P-1)%MOD,(Q-1)%MOD,1},
    };
    if (P+Q-3<0) mm[0][0] = 0;
    Mat stand;
    stand.clear();
    memcpy(stand.M,mm,sizeof(mm));
        for (i=0;i<8;i++){
            cin>>pos[i]>>p[i]>>q[i];
            pos[i]--;
            order[i] = i;
        }
        sort(order,order+8,cmp);
        ULL ans = 1;
        for (i=0;i<8;i++){
            if (i==7) len = (pos[order[0]]+L-pos[order[i]])%L-1;
            else len = (pos[order[i+1]]-pos[order[i]])-1;
            if (len==-1){
                if (p[order[i]]!=p[order[(i+1)%8]]||
                    q[order[i]]!=q[order[(i+1)%8]])
                {
                    ans = 0;
                    break;
                }else continue;
            }
            Mat R,res;
            R.clear(),res.clear();
            for (j=0;j<N;j++)
                res.M[j][j] = 1;
            copy(R,stand);
            while(len){
                if (len&1) Mmut(res,R);
                Mmut(R,R);
                len>>=1;
            }
            Mat init;
            init.clear();
            bool a = (p[order[i]]==p[(order[(i+1)%8])]);
            bool b = (q[order[i]]==q[(order[(i+1)%8])]);
            if (a&&b) init.M[0][3] = 1;
            else  if (b) init.M[0][1] = 1;
            else  if (a) init.M[0][2] = 1;
            else init.M[0][0] = 1;
            Mmut(init,res);
            ULL tmp = init.M[0][1]+init.M[0][2]+init.M[0][3];
            tmp%=MOD;
            ans*=tmp;
            ans%=MOD;
            //cout<<init.M[0][1]+init.M[0][2]+init.M[0][3]<<" "<<i<<endl;
        }
        cout<<ans<<endl;
    }
}