[블 루 브리지 컵 진제] 주사위 쌓 기 (행렬 쾌속 멱 최적화)

블 루 브리지 컵 진짜 문제. - 주사위 쌓 기.
도박 성 atm 은 만년 에 주사위 에 미련 을 두 었 다. 바로 주사 위 를 다른 위 에 쌓 는 것 이다. 비 뚤 어 져 서 는 안 되 고 네모 난 기둥 으로 쌓 아야 한다.
장기 적 인 관찰 을 통 해 아 톰 은 주사 위 를 안정 시 키 는 비밀 을 발견 했다. 어떤 숫자 가 붙 어 있 으 면 서로 배척 할 수 있다!먼저 주사 위 를 규범화 해 보 자. 11 의 맞은편 은 44, 22 의 맞은편 은 55, 33 의 맞은편 은 66 이다.만약 에 mm 조 가 서로 배척 하 는 현상 이 있다 고 가정 하면 각 조 의 두 숫자 면 이 붙 어 있 으 면 주사 위 는 안정 적 으로 쌓 이지 못 한다.atm 은 몇 가지 다른 주사위 방식 이 있 는 지 계산 하고 싶 습 니 다.두 가지 주사위 방식 이 같 고 이 두 가지 방식 에서 만 높이 에 대응 하 는 주사위 의 대응 숫자 방향 이 모두 같다.프로젝트 수가 너무 많 을 수 있 으 므 로 10 ^ 9 + 7 의 결 과 를 출력 하 십시오.
아 톰 의 주사위 수 를 얕 보지 마 세 요 ~
'입력 형식' 첫 번 째 줄 의 두 정수 n m n 은 주사위 의 수 를 다음 m 줄 로 표시 하고 줄 마다 두 개의 정수 a b 는 a 와 b 숫자 가 붙 어 있 지 않다 는 것 을 나타 낸다.
'출력 형식' 줄 의 한 수 는 답 모델 10 ^ 9 + 7 의 결 과 를 나타 낸다.
"샘플 입력" 2 1 1 2
"샘플 출력" 544
데이터 범위 30% 에 대한 데이터: n < = 5 대 60% 의 데이터: n < = 100 대 100% 의 데이터: 0 < n < = 10 ^ 9, m < = 36
 
제목:
n 개의 주사 위 는 세로 로 한 열 로 배열 해 야 한다. 1 의 맞은편 은 4, 2 의 맞은편 은 5, 3 의 맞은편 은 6 이다. 어떤 면 이 있 기 전에 서로 접촉 하지 말 아야 한다. 두 가지 배열 이 똑 같 고 각 층 의 주사위 의 각 방향 만 같다.-- 배열 방법 은 몇 가지 가 있 나.
생각:
가장 낮은 층 을 고려 하면 모든 면 이 위로 향 할 수 있 는데 이때 모든 면 이 위로 향 하 는 상황 은 1 이다.2 층 을 고려 할 때 우 리 는 면 1 과 면 2 가 서로 접촉 하지 못 한다 고 가정 한다. 즉, 앞의 1 차원 과 현재 차원 5 가 위로 올 라 가 는 상황 이 발생 하지 못 한다. 마찬가지 로 앞의 2 차원 과 현재 차원 4 가 위로 올 라 가 는 상황 도 발생 하지 못 한다.우 리 는 하나의 배열 로 이런 상황 을 기록 했다.우 리 는 모든 층 의 숫자 가 앞의 층 의 숫자 와 만 관계 가 있다 는 것 을 발견 할 수 있다.dp 로 이 문 제 를 해결 할 수 있 지만 아직 빠 르 지 않 습 니 다. 우 리 는 선형 대수 지식 으로 행렬 의 빠 른 멱 을 이용 하여 최적화 할 수 있 습 니 다.
행렬 A 를 만들어 서 현재 층 = 행렬 A 를 앞 층 으로 곱 해 야 합 니 다.피 보 나치 수열 을 예 로 들다
M21 (두 줄 한 열) {F [n], F [n - 1]} = M22 {1, 1, 0} * M21 {F [n - 1], F [n - 2]}
그래서 M21 {F [n], F [n - 1]} = M22 {1, 1, 1, 0} ^ (n - 2) * M21 {F [2], F [1]} 을 얻 을 수 있 습 니 다. 우 리 는 행렬 의 빠 른 속도 로 M22 {1, 1, 0} ^ (n - 2) 를 풀 수 있 습 니 다.
이 문제 도 비슷 한 해법 을 활용 한 것 이다.6 곱 하기 6 의 전이 행렬 a [i] [j], a [i] [j] = 1 을 고려 하면 현재 층 은 i 를 꼭대기 로 하고 앞 층 은 j 를 꼭대기 로 하 며 충돌 하지 않 으 며 반대로 충돌 하 는 것 을 나타 낸다.1 곱 하기 6 기초 행렬 의 b [i] 는 i 를 정면 으로 하 는 상황 수 를 나타 내 고 1 층 은 b1 이 며 b1 [i] = 1 이다.n 층 시 bn = b1 [i] * a [i] [j] ^ (n - 1).n 층 시 b [i] 를 모두 합치 면 방안 수 를 얻 을 수 있 습 니 다.앞의 몇 번 의 상 태 를 간단하게 검증 하면 이 방식 이 정확 하 다 는 것 을 알 수 있다.기타 세부 사항 은 코드 를 보십시오
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
struct matrix{
	int n,m;
	ll a[7][7];
};
matrix matrix_mul(matrix A,matrix B,int mod)
{
	matrix C;
	C.n=A.n;
	C.m=B.m;
	for(int i=1;i<=A.n;i++)
	{
		for(int j=1;j<=B.m;j++)
		{
			C.a[i][j]=0;
			for(int k=1;k<=A.m;k++)
			{
				C.a[i][j]+=(A.a[i][k]*B.a[k][j]%mod);
				C.a[i][j]%=mod;
			}
		}
	}
	return C;
}
matrix unit()
{
	matrix res;
	res.n=6;
	res.m=6;
	for(int i=1;i<=res.n;i++)
	{
		for(int j=1;j<=res.m;j++)
		{
			if(i==j)
			 res.a[i][j]=1;
			else 
			 res.a[i][j]=0;
		}
	}
	return res;
}
matrix matrix_pow(matrix A,int n,int mod)
{
	matrix res=unit(),temp=A;
	for(;n;n/=2)
	{
		if(n&1)res=matrix_mul(res,temp,mod);
		temp=matrix_mul(temp,temp,mod); 
	}
	return res;
}
ll pow_mod(ll a,int n,int mod)
{
	ll res=1,temp=a;
	for(;n;n/=2)
	{
		if(n&1)res=res*temp%mod;
		temp=temp*temp%mod;
	}
	return res;
}
int front[7]={0,4,5,6,1,2,3};
int main()
{ 
	int i,j,m,x,y;
	ll ans=0,n;
	scanf("%lld%d",&n,&m);
	matrix col;
	col.n=6;
	col.m=6;
	for(i=0;i<7;i++)
		for(j=0;j<7;j++)
			col.a[i][j]=1;
	for(i=0;i