江苏省网站建设哪家好,河南宝盈建设集团有限公司网站,做分类信息网站如何,wordpress 豆瓣电影注意到每个路线相邻车站的距离不超过K#xff0c;也就是说我们可以对连续K个车站的状态进行状压。 然后状压DP一下#xff0c;用矩阵快速幂加速运算即可。 #include stdio.h
#include stdlib.h
#include string.h
#include algorithm#define… 注意到每个路线相邻车站的距离不超过K也就是说我们可以对连续K个车站的状态进行状压。 然后状压DP一下用矩阵快速幂加速运算即可。 #include stdio.h
#include stdlib.h
#include string.h
#include algorithm#define MAXN 140
#define MOD 30031using namespace std;struct Matrix
{int num[MAXN][MAXN];int n,m; //n*m大小矩阵void setOne(int a,int b){na,mb;for(int i1;imin(n,m);i) num[i][i]1;}Matrix() { memset(num,0,sizeof(num)); }
}T,A,one;Matrix operator*(Matrix a,Matrix b)
{Matrix c;c.na.n,c.mb.m;for(int i1;ic.n;i)for(int j1;jc.m;j)for(int k1;ka.m;k)c.num[i][j](c.num[i][j]a.num[i][k]*b.num[k][j])%MOD;return c;
}Matrix fastPow(Matrix base,int pow)
{Matrix ans;ans.setOne(base.n,base.m);while(pow){if(pow1) ansans*base;basebase*base;pow1;}return ans;
}int calc(int x) //计算x的二进制中1的个数
{int sum0;while(x){sum;x-x(-x); //x去掉最后一个1}return sum;
}int n,k,p,goal; //goal是目标状态bool canConvert(int to,int from) //检查状态from能否一步转移到状态to
{from(from-(1(p-1)))1; //这一步相当于把from向左推了一位个位用0补齐int tmpfrom^to; //tmp应该只有一个1if(tmp(tmp(-tmp))) return true; //tmp只有一个1则是合法的return false; //否则是不合法的
}int status[MAXN],top0; //保存所有DP过程中可能出现的状态的栈int main()
{scanf(%d%d%d,n,k,p);for(int S(1(p-1));S(1p);S) //枚举DP状态S,S是合法状态当且仅当S的二进制中1的个数恰好为k{if(calc(S)k){status[top]S;if(S(1p)-1-((1(p-k))-1)) goaltop; //S是最终要达到的状态}}for(int i1;itop;i)for(int j1;jtop;j)if(canConvert(status[i],status[j]))T.num[i][j]1;A.nA.mT.nT.mtop;A.num[1][goal]1;TfastPow(T,n-k);AA*T;printf(%d\n,A.num[1][goal]);return 0;
} View Code 转载于:https://www.cnblogs.com/lishiyao/p/6882236.html
