题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 6;
#define int long long
int n,m=1e9+7;
void mul(int c[],int a[],int b[][N]){
int temp[N]={0};
for(int i=0;i<N;i++){//列
for(int j=0;j<N;j++){//行
temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
}
}
memcpy(c,temp,sizeof(temp));
}
void mul(int c[][N],int a[][N],int b[][N]){
int temp[N][N]={0};
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=0;k<N;k++){
temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
}
}
}
memcpy(c,temp,sizeof(temp));
}
int b[50][50];
void solve(){
int k;
cin>>n>>k;
for(int i=1;i<=k;i++){
int x,y;cin>>x>>y;
x--;y--;
b[x][y]=b[y][x]=1;
}
// int f1[N] = {0,0,0,0,0,0,1,1,1,1,1,1};
// int a[N][N] = {
// {0,0,0,0,0,0,0,0,0,0,0,0},
// {0,0,0,0,0,0,0,0,0,0,0,0},
// {0,0,0,0,0,0,0,0,0,0,0,0},
// {0,0,0,0,0,0,0,0,0,0,0,0},
// {0,0,0,0,0,0,0,0,0,0,0,0},
// {0,0,0,0,0,0,0,0,0,0,0,0},//6
// {1,0,0,0,0,0,0,0,0,0,0,0},
// {0,1,0,0,0,0,0,0,0,0,0,0},
// {0,0,1,0,0,0,0,0,0,0,0,0},
// {0,0,0,1,0,0,0,0,0,0,0,0},
// {0,0,0,0,1,0,0,0,0,0,0,0},
// {0,0,0,0,0,1,0,0,0,0,0,0},
// };
//1 4
//2 5
//3 6
int f1[N] = {4,4,4,4,4,4};
int a[N][N] = {
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,0},
};
const int op[6]={3,4,5,0,1,2};
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
if(b[i][op[j]]==0)
{
a[j][i]=4;
}
}
}
n--;
while (n)
{
if (n & 1) mul(f1, f1, a); // res = res * a
mul(a, a, a); // a = a * a
n >>= 1;
}
int res=0;
for(int i=0;i<N;i++)
res=(res+f1[i])%m;
cout << res << endl;
}
signed main(){
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla