2012-0017
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
占by ZhouYuChen
题意是说，一个正多边形有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;
}
}}}
---------------------------------------------------------------我是无辜的分割线-----------------------------------------------------------------------------------------
学长好快，仰慕学长。
题意学长已经说了，这里便不作多余阐述。
题目中一个关键条件便是相邻两点之间，两种属性至少有一个相同。利用这个条件，我们可以把问题变成，在一个K*S的棋盘上，从某点出发，每次走到同行同列的任意一个点上。求从一个点出发走N步后回到原点的方案数，当中8步一定要走到某些给定的点（有冲突的可以预处理掉，当然算法够健壮也可以直接处理掉）。不难发现（也可以人肉做几组观察）到棋盘上的点可以分成四种：起点，与起点同行不同列，与起点同列不同行，与起点不同列不同行。记走N步后走到点(x,y)的方案数为f(N,x,y)，不难发现，若(x1,y1)与(x2,y2)是同类点，则 f(N,x1,y1) == f(N,x2,y2)。这个性质可以用数学归纳法证明（搞ACM嘛。。。就不要那么多复杂的证明了，能用就好,匿了）
于是就变成四个变量推来推去的问题，用矩阵乘法便可以迅速解决，具体矩阵的构造可以看LS，方法有很多种。最后按给定的点把递推分成八个部分去做。
注意题目中该用long long就果断用。。。
最后贴上自己巨土的代码
{{{
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
struct matrix{long long a[5][5];};
struct node{long long x,y,k;};
node c[9];
matrix origin,s,bi;
const long long mod = 1234567890;
long long n,k,i,v;
using namespace std;
matrix mul(matrix a,matrix b)
{
matrix c;
memset(c.a,0,sizeof(c.a));
int i,j,k;
for (i=1;i<=4;i++)
for (j=1;j<=4;j++)
for (k=1;k<=4;k++)
{
c.a[i][j]=(c.a[i][j]+ a.a[i][k]*b.a[k][j] ) % mod;
}
return c;
}
matrix cnt(matrix& k,long long s)
{
if (s == 1) return k;
if (!s) return bi;
matrix x=cnt(k,s/2);
if (s%2) return mul(mul(x,x),origin);
else return mul(x,x);
}
bool cmp(node a,node b)
{
return a.k < b.k;
}
int main()
{
while (cin >> n >> k >> v)
{
for (i=1;i<=8;i++) cin >> c[i].k >> c[i].x >> c[i].y;
sort(c+1,c+9,cmp);
// for (i=1;i<=8;i++) cout << c[i].k << " " << c[i].x << " " << c[i].y << endl;
origin.a[1][1]=1;
origin.a[1][2]=1;
origin.a[1][3]=1;
origin.a[1][4]=0;
origin.a[2][1]=(k-1)% mod;
origin.a[2][2]=(k-1) % mod;
origin.a[2][3]=0;
origin.a[2][4]=1;
origin.a[3][1]=(v-1)% mod;
origin.a[3][2]=0;
origin.a[3][3]=(v-1) % mod;
origin.a[3][4]=1;
origin.a[4][1]=0;
origin.a[4][2]=(v-1) % mod;
origin.a[4][3]=(k-1) % mod;
origin.a[4][4]=(k+v-3) % mod;
bi.a[1][1]=1;
bi.a[2][2]=1;
bi.a[3][3]=1;
bi.a[4][4]=1;
matrix ss;
long long ans=1;
for (i=1;i<8;i++)
{
// cout << ans << endl;
ss=cnt(origin,c[i+1].k-c[i].k);
if (c[i+1].x == c[i].x && c[i+1].y == c[i].y)
{
ans=ans*ss.a[1][1] % mod;
}
else if (c[i+1].x == c[i].x)
{
ans=ans*ss.a[1][3] % mod;
}
else if (c[i+1].y == c[i].y)
{
ans=ans*ss.a[1][2] % mod;
}
else
{
ans=ans*ss.a[1][4] % mod;
}
} // end for
ss=cnt(origin,c[1].k-c[i].k+n);
if (c[1].x == c[i].x && c[1].y == c[i].y)
{
ans=ans*ss.a[1][1] % mod;
}
else if (c[1].x == c[i].x)
{
ans=ans*ss.a[1][3] % mod;
}
else if (c[1].y == c[i].y)
{
ans=ans*ss.a[1][2] % mod;
}
else
{
ans=ans*ss.a[1][4] % mod;
}
cout << ans % mod << endl;
}
return 0;
}
}}}占by ZhouYuChen
题意是说，一个正多边形有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;
}
我是无辜的分割线
学长好快，仰慕学长。
题意学长已经说了，这里便不作多余阐述。
题目中一个关键条件便是相邻两点之间，两种属性至少有一个相同。利用这个条件，我们可以把问题变成，在一个K*S的棋盘上，从某点出发，每次走到同行同列的任意一个点上。求从一个点出发走N步后回到原点的方案数，当中8步一定要走到某些给定的点（有冲突的可以预处理掉，当然算法够健壮也可以直接处理掉）。不难发现（也可以人肉做几组观察）到棋盘上的点可以分成四种：起点，与起点同行不同列，与起点同列不同行，与起点不同列不同行。记走N步后走到点(x,y)的方案数为f(N,x,y)，不难发现，若(x1,y1)与(x2,y2)是同类点，则 f(N,x1,y1) == f(N,x2,y2)。这个性质可以用数学归纳法证明（搞ACM嘛。。。就不要那么多复杂的证明了，能用就好,匿了）
于是就变成四个变量推来推去的问题，用矩阵乘法便可以迅速解决，具体矩阵的构造可以看LS，方法有很多种。最后按给定的点把递推分成八个部分去做。
注意题目中该用long long就果断用。。。
最后贴上自己巨土的代码
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<algorithm>
struct matrix{long long a[5][5];};
struct node{long long x,y,k;};
node c[9];
matrix origin,s,bi;
const long long mod = 1234567890;
long long n,k,i,v;
using namespace std;
matrix mul(matrix a,matrix b)
{
matrix c;
memset(c.a,0,sizeof(c.a));
int i,j,k;
for (i=1;i<=4;i++)
for (j=1;j<=4;j++)
for (k=1;k<=4;k++)
{
c.a[i][j]=(c.a[i][j]+ a.a[i][k]*b.a[k][j] ) % mod;
}
return c;
}
matrix cnt(matrix& k,long long s)
{
if (s == 1) return k;
if (!s) return bi;
matrix x=cnt(k,s/2);
if (s%2) return mul(mul(x,x),origin);
else return mul(x,x);
}
bool cmp(node a,node b)
{
return a.k < b.k;
}
int main()
{
while (cin >> n >> k >> v)
{
for (i=1;i<=8;i++) cin >> c[i].k >> c[i].x >> c[i].y;
sort(c+1,c+9,cmp);
// for (i=1;i<=8;i++) cout << c[i].k << " " << c[i].x << " " << c[i].y << endl;
origin.a[1][1]=1;
origin.a[1][2]=1;
origin.a[1][3]=1;
origin.a[1][4]=0;
origin.a[2][1]=(k-1)% mod;
origin.a[2][2]=(k-1) % mod;
origin.a[2][3]=0;
origin.a[2][4]=1;
origin.a[3][1]=(v-1)% mod;
origin.a[3][2]=0;
origin.a[3][3]=(v-1) % mod;
origin.a[3][4]=1;
origin.a[4][1]=0;
origin.a[4][2]=(v-1) % mod;
origin.a[4][3]=(k-1) % mod;
origin.a[4][4]=(k+v-3) % mod;
bi.a[1][1]=1;
bi.a[2][2]=1;
bi.a[3][3]=1;
bi.a[4][4]=1;
matrix ss;
long long ans=1;
for (i=1;i<8;i++)
{
// cout << ans << endl;
ss=cnt(origin,c[i+1].k-c[i].k);
if (c[i+1].x == c[i].x && c[i+1].y == c[i].y)
{
ans=ans*ss.a[1][1] % mod;
}
else if (c[i+1].x == c[i].x)
{
ans=ans*ss.a[1][3] % mod;
}
else if (c[i+1].y == c[i].y)
{
ans=ans*ss.a[1][2] % mod;
}
else
{
ans=ans*ss.a[1][4] % mod;
}
} // end for
ss=cnt(origin,c[1].k-c[i].k+n);
if (c[1].x == c[i].x && c[1].y == c[i].y)
{
ans=ans*ss.a[1][1] % mod;
}
else if (c[1].x == c[i].x)
{
ans=ans*ss.a[1][3] % mod;
}
else if (c[1].y == c[i].y)
{
ans=ans*ss.a[1][2] % mod;
}
else
{
ans=ans*ss.a[1][4] % mod;
}
cout << ans % mod << endl;
}
return 0;
}