2012-A3-0017
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意是说，一个正多边形有N个点，每个点有2个属性值（1..P，1..Q），相邻两个点必须有一种属性相同。
给出8个点的属性，求样的正多边形数量。
首先要判掉一些可能的trick，比如8个点有重，给的点有直接相邻，P=1，或 Q=1，那么答案是另一个维度Q(P)的(N-(确定点个数的次方））次方。
然后可以在两端确定的情况下，计算中间不确定的点的数量。
然后根据属性值的在1..P,1..Q 任意值都是等价的，只要处理，两端属性是否有若干维相同就可以。
比如一端是(A,B)，中间有L个待填。用x,y表示一个状态。x != A ,y != B.
那么另一端和中间的，可表示成 xy ,xB ,Ay,AB，这段可一根据他的状态表示成一个列矩阵M[0],比如Ay就是 [0 0 1 0]T，表示在各种状态下的数量。
那么就可以如此题目的约束写出递推阵。
M[n+1] = D * M[n]
其中D =
[
{{{
P+Q-3 Q-1 P-1 0
1 P-1 0 P-1
1 0 Q-1 Q-1
0 1 1 1
}}}
]
比如n+1状态是AB 上一个只可能是Ay xB AB ： (AB)_(n+1) = (Ay)_(n) + (xB)_(n) + (AB)_(n),
如果是 xB 上一个是 xy xB AB x有P-1种，于是 (xB)_(n+1) = (xy)_(n)*(P-1) + (xB)_(n)*(P-1) + (AB)_(n).
检查矩阵是否正确，要算每一列，的和是不是P+Q-1。一个点与上个点可以相邻有P+Q-1中情况。
在长度为L的不缺定的情况下，第L个的状态是M[L] = D^L^ * M[0];
然后看端点AB，答案就是 (AB)_(L) +(Ay)_(L) + (xB)_(L)
{{{
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
typedef unsigned long long num;
const num M=1234567890;
num N,P,Q;
num jc[40][4][4];
num num_pow(num a,num n){
num ret = 1;
a%=M;
for(;n;n>>=1){
if(n&1)ret=ret*a%M;
a=a*a%M;
}
return ret;
}
void mul(num z[][4],num x[][4],num y[][4]){
memset(z,0,sizeof(num)*16);
for(size_t i=0;i<4;++i)
for(size_t j=0;j<4;++j)
for(size_t k=0;k<4;++k)
z[i][j]=(z[i][j]+x[i][k]*y[k][j])%M;
}
void mul_eq(num z[][4],num x[][4]){
static num tmp[4][4];
memcpy(tmp,z,sizeof(tmp));
mul(z,tmp,x);
}
num gao(num L,bool eq1,bool eq2){
if(L==0)
return (eq1||eq2)?1:0;
if(P==1||Q==1)
return num_pow((P+Q-1)%M,L);
static num ret[4][4];
memset(ret,0,sizeof(ret));
for(int i=0;i<4;++i)ret[i][i]=1;
num t[4][4];mul(t,ret,ret);
for(int i=0;i<40;++i)
if(1ull<<i & L)
mul_eq(ret,jc[i]);
return ret[1][(eq1?2:0)+(eq2?1:0)]+ret[2][(eq1?2:0)+(eq2?1:0)]+ret[3][(eq1?2:0)+(eq2?1:0)];
}
num x[8],u[8],v[8];
num solve(){
#define mp make_pair
for(int i=0;i<8;++i)
scanf("%lld%lld%lld",x+i,u+i,v+i);
map<num,pair<num,num> > ss;
for(int i=0;i<8;++i)
if(ss.count(x[i])){
if(ss[x[i]]!= mp(u[i],v[i]))return 0;
}
else ss[x[i]]=mp(u[i],v[i]);
int m = 0;
num a[4][4]={
{(P+Q-3+M)%M, (Q-1)%M,(P-1)%M,0},
{1,(P-1)%M,0,(P-1)%M},
{1,0,(Q-1)%M,(Q-1)%M},
{0,1,1,1}
};
memcpy(jc[0],a,sizeof(a));
for(int i =1;i<=40;++i)
mul(jc[i],jc[i-1],jc[i-1]);
for(__typeof(ss.begin()) it=ss.begin();it!=ss.end();++it,++m){
x[m]=it->first;
u[m]=it->second .first;
v[m]=it->second .second;
}
num ans = 1;
for(size_t i=1;i<m;++i)
ans = ans * gao(x[i]-x[i-1]-1,(u[i-1]==u[i]),(v[i-1]==v[i])) % M;
ans =ans * gao(x[0]+N-x[m-1]-1,(u[m-1]==u[0]),(v[m-1]==v[0]))%M;
return ans;
}
int main(){
for(;scanf("%lld%lld%lld",&N,&P,&Q)==3;)
printf("%lld\n",solve());
return 0;
}
}}}
{{{
学长你的矩阵D我还是没有看明白。。M矩阵是[xy ,xB ,Ay,AB]的情况下，我推出来的矩阵D和猛犸学长一样，是
{p+q-3, 1 , 1 ,0},
{ q-1 ,p-1, 0 ,1},
{ p-1 , 0 ,q-1,1},
{ 0 ,p-1,q-1,1},
求解释@.@
比如xB转移到xy的情况，由于B变成y肯定导致不同，所以x一定要相同，因此有q-1种变法，为什么学长的矩阵里是1？
by 大肥羊
}}}
{{{区别在计算时变换矩阵是左乘还是右乘}}}
我的习惯比较倾向于 D^n^×X，X是个列向量，这样和很多教材中的表达方式一致
你给的矩阵应该是一个行向量Y×E^n^这样。而这样表述的话，D=E^T^,X=Y^T^,二者表达的意思应该是一样的。
在我的矩阵里xB变成xy的情况应该是看第一行的第2列，也是Q-1.
{{{
啊~我明白了~果然还是我对矩阵乘法的理解不扎实@.@ by大肥羊
}}}题意是说，一个正多边形有N个点，每个点有2个属性值（1..P，1..Q），相邻两个点必须有一种属性相同。
给出8个点的属性，求样的正多边形数量。
首先要判掉一些可能的trick，比如8个点有重，给的点有直接相邻，P=1，或 Q=1，那么答案是另一个维度Q(P)的(N-(确定点个数的次方））次方。
然后可以在两端确定的情况下，计算中间不确定的点的数量。
然后根据属性值的在1..P,1..Q 任意值都是等价的，只要处理，两端属性是否有若干维相同就可以。
比如一端是(A,B)，中间有L个待填。用x,y表示一个状态。x != A ,y != B.
那么另一端和中间的，可表示成 xy ,xB ,Ay,AB，这段可一根据他的状态表示成一个列矩阵M[0],比如Ay就是 [0 0 1 0]T，表示在各种状态下的数量。
那么就可以如此题目的约束写出递推阵。
M[n+1] = D * M[n]
其中D =
[
P+Q-3 Q-1 P-1 0
1 P-1 0 P-1
1 0 Q-1 Q-1
0 1 1 1
]
比如n+1状态是AB 上一个只可能是Ay xB AB ： (AB)_(n+1) = (Ay)_(n) + (xB)_(n) + (AB)_(n),
如果是 xB 上一个是 xy xB AB x有P-1种，于是 (xB)_(n+1) = (xy)_(n)*(P-1) + (xB)_(n)*(P-1) + (AB)_(n).
检查矩阵是否正确，要算每一列，的和是不是P+Q-1。一个点与上个点可以相邻有P+Q-1中情况。
在长度为L的不缺定的情况下，第L个的状态是M[L] = DL * M[0];
然后看端点AB，答案就是 (AB)_(L) +(Ay)_(L) + (xB)_(L)
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
typedef unsigned long long num;
const num M=1234567890;
num N,P,Q;
num jc[40][4][4];
num num_pow(num a,num n){
num ret = 1;
a%=M;
for(;n;n>>=1){
if(n&1)ret=ret*a%M;
a=a*a%M;
}
return ret;
}
void mul(num z[][4],num x[][4],num y[][4]){
memset(z,0,sizeof(num)*16);
for(size_t i=0;i<4;++i)
for(size_t j=0;j<4;++j)
for(size_t k=0;k<4;++k)
z[i][j]=(z[i][j]+x[i][k]*y[k][j])%M;
}
void mul_eq(num z[][4],num x[][4]){
static num tmp[4][4];
memcpy(tmp,z,sizeof(tmp));
mul(z,tmp,x);
}
num gao(num L,bool eq1,bool eq2){
if(L==0)
return (eq1||eq2)?1:0;
if(P==1||Q==1)
return num_pow((P+Q-1)%M,L);
static num ret[4][4];
memset(ret,0,sizeof(ret));
for(int i=0;i<4;++i)ret[i][i]=1;
num t[4][4];mul(t,ret,ret);
for(int i=0;i<40;++i)
if(1ull<<i & L)
mul_eq(ret,jc[i]);
return ret[1][(eq1?2:0)+(eq2?1:0)]+ret[2][(eq1?2:0)+(eq2?1:0)]+ret[3][(eq1?2:0)+(eq2?1:0)];
}
num x[8],u[8],v[8];
num solve(){
#define mp make_pair
for(int i=0;i<8;++i)
scanf("%lld%lld%lld",x+i,u+i,v+i);
map<num,pair<num,num> > ss;
for(int i=0;i<8;++i)
if(ss.count(x[i])){
if(ss[x[i]]!= mp(u[i],v[i]))return 0;
}
else ss[x[i]]=mp(u[i],v[i]);
int m = 0;
num a[4][4]={
{(P+Q-3+M)%M, (Q-1)%M,(P-1)%M,0},
{1,(P-1)%M,0,(P-1)%M},
{1,0,(Q-1)%M,(Q-1)%M},
{0,1,1,1}
};
memcpy(jc[0],a,sizeof(a));
for(int i =1;i<=40;++i)
mul(jc[i],jc[i-1],jc[i-1]);
for(__typeof(ss.begin()) it=ss.begin();it!=ss.end();++it,++m){
x[m]=it->first;
u[m]=it->second .first;
v[m]=it->second .second;
}
num ans = 1;
for(size_t i=1;i<m;++i)
ans = ans * gao(x[i]-x[i-1]-1,(u[i-1]==u[i]),(v[i-1]==v[i])) % M;
ans =ans * gao(x[0]+N-x[m-1]-1,(u[m-1]==u[0]),(v[m-1]==v[0]))%M;
return ans;
}
int main(){
for(;scanf("%lld%lld%lld",&N,&P,&Q)==3;)
printf("%lld\n",solve());
return 0;
}
学长你的矩阵D我还是没有看明白。。M矩阵是[xy ,xB ,Ay,AB]的情况下，我推出来的矩阵D和猛犸学长一样，是
{p+q-3, 1 , 1 ,0},
{ q-1 ,p-1, 0 ,1},
{ p-1 , 0 ,q-1,1},
{ 0 ,p-1,q-1,1},
求解释@.@
比如xB转移到xy的情况，由于B变成y肯定导致不同，所以x一定要相同，因此有q-1种变法，为什么学长的矩阵里是1？
by 大肥羊
区别在计算时变换矩阵是左乘还是右乘
我的习惯比较倾向于 Dn×X，X是个列向量，这样和很多教材中的表达方式一致
你给的矩阵应该是一个行向量Y×En这样。而这样表述的话，D=ET,X=YT,二者表达的意思应该是一样的。
在我的矩阵里xB变成xy的情况应该是看第一行的第2列，也是Q-1.
啊~我明白了~果然还是我对矩阵乘法的理解不扎实@.@ by大肥羊