当前位置:网站首页>Lattice coloring - matrix fast power optimized shape pressure DP
Lattice coloring - matrix fast power optimized shape pressure DP
2022-07-07 08:01:00 【Wawa source】
Topic link
Normal embossing , But it's easy to see that the data is outrageous , This is bound to fail , It needs to be optimized
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 6 ,M = 1<<5,mod=1e9+7;
int n,m;
int f[110][M];
signed main()
{
cin>>n>>m;
for(int i=0;i<1<<n;i++)f[1][i]=1;
// 0 It's black 1 yes white
for(int i=2;i<=m;i++)
{
for(int j=0;j<1<<n;j++)
{
for(int k=0;k<1<<n;k++)
{
if(j&k)continue;
if((j|k)==0)continue;
f[i][j]=(f[i][j]+f[i-1][k])%mod;
}
}
}
int res=0;
for(int i=0;i<1<<n;i++)res+=f[m][i];
cout<<res<<endl;
}
Fast power optimization method of matrix
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 1<<5,mod=1e9+7;
int n,m;
int a[N][N],b[N][N];
void mul(int a[][N],int b[][N])
{
int tmp[N][N]={
0};
for(int i=0;i<1<<n;i++)
for(int j=0;j<1<<n;j++)
for(int k=0;k<1<<n;k++)
tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
for(int i=0;i<1<<n;i++)
for(int j=0;j<1<<n;j++)
a[i][j]=tmp[i][j];
}
signed main()
{
cin>>n>>m;
// The initial state
for(int i=0;i<1<<n;i++)a[i][i]=1;
// 0 black
// 1 white
for(int i=0;i<1<<n;i++)
{
for(int j=0;j<1<<n;j++)
{
if(i&j)continue;
if((i|j)==0)continue;
b[i][j]=1;
}
}
m--;
while(m)
{
if(m&1)mul(a,b);
mul(b,b);
m>>=1;
}
int res=0;
for(int i=0;i<1<<n;i++)
for(int j=0;j<1<<n;j++)
res=(res+a[i][j])%mod;
cout<<res<<'\n';
}
边栏推荐
猜你喜欢
[P2P] local packet capturing
MySQL multi column index (composite index) features and usage scenarios
QT learning 28 toolbar in the main window
2022制冷与空调设备运行操作复训题库及答案
You Li takes you to talk about C language 6 (common keywords)
2022 simulated examination question bank and online simulated examination of tea master (primary) examination questions
Linux server development, detailed explanation of redis related commands and their principles
Hands on deep learning (IV) -- convolutional neural network CNN
Who has docker to install MySQL locally?
Shell 脚本的替换功能实现
随机推荐
pytest+allure+jenkins環境--填坑完畢
Mysql高低版本切换需要修改的配置5-8(此处以aicode为例)
[UVM foundation] what is transaction
Linux server development, MySQL index principle and optimization
[quick start of Digital IC Verification] 15. Basic syntax of SystemVerilog learning 2 (operators, type conversion, loops, task/function... Including practical exercises)
【webrtc】m98 screen和window采集
2022 recurrent training question bank and answers of refrigeration and air conditioning equipment operation
[Matlab] Simulink 自定义函数中的矩阵乘法工作不正常时可以使用模块库中的矩阵乘法模块代替
Few-Shot Learning && Meta Learning:小样本学习原理和Siamese网络结构(一)
Live online system source code, using valueanimator to achieve view zoom in and out animation effect
Numbers that appear only once
Qt学习26 布局管理综合实例
Linux server development, MySQL transaction principle analysis
JS quick start (I)
Chip design data download
【VHDL 并行语句执行】
Qt学习28 主窗口中的工具栏
2022年全国最新消防设施操作员(初级消防设施操作员)模拟题及答案
探索Cassandra的去中心化分布式架构
Main window in QT learning 27 application