安徽做公司网站哪家好,业之峰装饰公司口碑,注册一个公司多少钱,网页设计网站模板素材七十分超时代码#xff0c;具体思路可以仿照acwing蒙德里安的梦想 就是枚举第i层放 a #xff0c;第i-1层放b的合法方案其中b和a都是同一块#xff1b; #include iostream
#include algorithm
#include cstring
#include sstream
using nam…七十分超时代码具体思路可以仿照acwing蒙德里安的梦想 就是枚举第i层放 a 第i-1层放b的合法方案其中b和a都是同一块 #include iostream
#include algorithm
#include cstring
#include sstream
using namespace std;
typedef long long LL;
const int N 5e5 4, mod 1e9 7, M 17;LL n;
int m;
int dp[N][M];void dfs(int a, int b, int p)
{if(p m) v[a][b], c[a][b];else{if(p 0){if(!((ap1)||(bp1)||(bp-11)))dfs(a|1p, b|1p|1p-1, p1);if(!((ap1)||(bp1)||(ap-11)))dfs(a|1p|1p-1, b|1p, p1);}if(p1 ! m){if(!((ap1)||(bp1)||(bp11)))dfs(a|1p, b|1p|1p1, p1);if(!((ap1)||(bp1)||(ap11)))dfs(a|1p|1p1, b|1p, p1);}dfs(a, b, p1);}
}int main()
{scanf(%lld%d, n, m);dfs(0, 0, 0);for(int i 0;i 1m;i )dp[1][i] v[i][(1m)-1];for(int i 2;i n;i)for(int j 0;j 1m;j )for(int k 0;k 1m;k )dp[i][j] (dp[i][j] (LL)dp[i-1][((1m)-1)^k]*v[j][k])%mod;coutdp[n-1][(1m)-1];return 0;
}100 分矩阵快速幂
#include iostream
#include algorithm
#include cstring
#include sstream
using namespace std;
typedef long long LL;
const int N 5e5 4, mod 1e9 7, M 17;LL n;
int m, c[M][M], tem[M][M], res[M][M];
int dp[3][M];void multi(int a[][M], int b[][M], int n)
{memset(tem, 0, sizeof tem); for(int i 0;i n;i )for(int j 0;j n;j )for(int k 0;k n;k )tem[i][j] (tem[i][j] (LL)a[i][k]*b[k][j])%mod;for(int i 0;i n;i )for(int j 0;j n;j )a[i][j] tem[i][j];
}void pow(int a[][M], LL n)
{memset(res, 0, sizeof res);for(int i 0;i 1m;i )res[i][i] 1;while(n){if(n1) multi(res, a, 1m);multi(a, a, 1m);n1;}
}void dfs(int a, int b, int p)
{if(p m) c[a][((1m)-1)^b]; // 方便 矩阵快速幂 这题c[i][j]代表第二层是i 第一层是i的合法方案的其他空缺 else{if(p 0){if(!((ap1)||(bp1)||(bp-11)))dfs(a|1p, b|1p|1p-1, p1);if(!((ap1)||(bp1)||(ap-11)))dfs(a|1p|1p-1, b|1p, p1);}if(p1 ! m){if(!((ap1)||(bp1)||(bp11)))dfs(a|1p, b|1p|1p1, p1);if(!((ap1)||(bp1)||(ap11)))dfs(a|1p|1p1, b|1p, p1);}dfs(a, b, p1);}
}int main()
{scanf(%lld%d, n, m);dfs(0, 0, 0);for(int i 0;i 1m;i )dp[1][i] c[i][0];if(n 2)pow(c, n-2); for(int i 0;i 1m;i )dp[2][(1m)-1] (dp[2][(1m)-1] (LL)res[(1m)-1][i]*dp[1][i])%mod;coutdp[2][(1m)-1];return 0;
}
