首页 > 其他分享 >DPR Walk

DPR Walk

时间:2023-11-22 17:14:28浏览次数:55  
标签:Matrix int DPR long Walk include mod

题意

给定一个无向图,求路径长度为 \(k\) 的路径条数。

\(n \le 50\)。

Sol

考虑 \(dp\),设 \(f_{i, j}\) 表示从 \(i \to j\) 的路径长为 \(k\) 的方案数。

不难发现转移即为矩阵乘法。

直接快速幂即可。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 55, mod = 1e9 + 7;

void Mod(int &x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

struct Matrix {

int A[N][N];
int n, m;

int* operator [](int x) {
	return A[x];
}

Matrix (int n_, int m_) {
	for (int i = 1; i <= n_; i++)
		for (int j = 1; j <= m_; j++)
			A[i][j] = 0;
	n = n_, m = m_;
}

Matrix (int n_, int m_, int flg) {
	for (int i = 1; i <= n_; i++)
		for (int j = 1; j <= m_; j++)
			A[i][j] = 0;
	for (int i = 1; i <= n_; i++)
		A[i][i] = 1;
	n = n_, m = m_;
}

friend Matrix operator *(Matrix a, Matrix b) {
	Matrix ans(a.n, b.m);
	for (int i = 1; i <= a.n; i++)
		for (int j = 1; j <= a.m; j++)
			for (int k = 1; k <= b.m; k++)
				ans[i][j] += a[i][k] * b[k][j] % mod, Mod(ans[i][j]);
	return ans;
}

friend Matrix operator ^(Matrix x, int k) {
	Matrix ans(x.n, x.m, 1);
	while (k) {
		if (k & 1) ans = ans * x;
		x = x * x;
		k >>= 1;
	}
	return ans;
}

};

signed main() {
	int n = read(), k = read();
	Matrix T(n, n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			T[i][j] = read();
	T = T ^ k;
	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			ans += T[i][j], Mod(ans);
	write(ans), puts("");
	return 0;
}

标签:Matrix,int,DPR,long,Walk,include,mod
From: https://www.cnblogs.com/cxqghzj/p/17849773.html

相关文章

  • UnhandledPromiseRejectionWarning: SyntaxError: Unexpected token '??=' 报错处理
    在用vite创建react的时候install完成后输入pnpmrundev突然蹦出UnhandledPromiseRejectionWarning:SyntaxError:Unexpectedtoken'??='一脸闷逼,百度了一下。哦吼,逻辑空赋值(??=)是ES2021的语法,nodev15.0.0以上才支持逻辑空赋值(??=)的语法。之前为了兼容旧代码使用的n......
  • centos:subprocess.CalledProcessError: Command ‘[‘ninja‘, ‘-v‘]‘ returned n
    一、原因pytorch版本大于1.5二、解决1、降低pytorch版本将pytorch版本降到1.5以下2、禁用ninjiapytorch默认使用ninjia作为backend,将其禁用。替换为以下代码setup(...,cmdclass={#'build_ext':BuildExtension,'build_ext':BuildExtension.w......
  • skywalking(三) 实现收集基于虚拟机环境dubbo微服务链路跟踪案例
    dubbo微服务架构https://cn.dubbo.apache.org/zh-cn/overview/home/https://help.aliyun.com/zh/edas/developer-reference/dubbo-overview‍1.安装zookeeper注册中心官网:https://zookeeper.apache.org/安装说明:https://zookeeper.apache.org/doc/r3.7.1/zookeeperAdmin.......
  • skywalking(二) 实现基于nginx+java服务的全链路数据收集
    实现nginx+jenkins全链路数据追踪1.部署JenkinsIP:10.0.0.941.1安装、配置jenkins#1.安装jdk11aptupdateaptinstall-yopenjdk-11-jdk#2.下载tomcatmdkir/apps&cd/appswgethttps://dlcdn.apache.org/tomcat/tomcat-8/v8.5.93/bin/apache-tomcat-8.5.93.tar.g......
  • WordPress主题 JustNews主题6.0.1(亲测首页不空白)
    介绍资源入口需要用WordPress5.X版本JustNews介绍:一款专为博客、自媒体、资讯类的网站设计开发的WordPress主题,自v3.0版开始支持自主研发的前端用户中心,不仅支持注册、登录、账户设置、个人中心等常用页面的添加,还可以上传头像、设置用户分组等等!更新介绍JustNews主题更新......
  • 部署skywalking-8.9
    skywalking服务器资源下载地址:https://archive.apache.org/dist/skywalking/8.9.0/解压:tar-zxvfapache-skywalking-apm-8.9.0.tar.gz修改默认端口:viapache-skywalking-apm-bin/config/application.yml 修改默认存储:viapache-skywalking-apm-bin/webapp/webapp.yml......
  • AND-MEX Walk
    这个题解不错。首先,10万组询问,10万的点和边,能且仅能用并查集判断图的连通性。看到&就要想到非严格单调递减,看到|就要想到非严格单调递增。不难发现样例中答案只有0,1,2,仔细想想,就会发现不可能存在210的序列,因为一旦有了2,末尾就一定是0,和任何数&都不可能是1。换......
  • wordpress SQL
     UPDATEwp_postsSETpost_content=REPLACE(post_content,"192.168.120.126:8000","计算机名:8000")  WHEREid=10 ;   修改ip地址后,导致图片失效 报语法错,跟mysql版本没有关系。   更改ip和切换主题都会导致文章排版和图片问题。有些主题是用markdown,有......
  • WordPress主题警告:侧边栏字符串偏移非法
    "侧边栏字符串偏移非法"警告通常是由于在WordPress主题的侧边栏中使用了不正确的代码或字符引起的。这可能是一个语法错误、字符编码问题或标签的闭合问题。要解决这个问题,可以尝试以下几个步骤:1.检查语法错误:打开你的WordPress主题文件,找到侧边栏的相关代码,并确保没有任何语法错......
  • 虚拟机,宝塔面板,wordpress
    1.进入并安装宝塔面板,linux面板安装脚本;2.选择对应的Linux版本,复制命令到虚拟机命令行执行;编者用的是centos,选择第一个脚本;3.安装结束后,会得到如下信息,复制内网面板地址,在运行虚拟机的主机上的浏览器中,进入该地址,输入对应的用户名username,密码password;安装插件选择对应的LNMP......