cp-lib

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Dusker233/cp-lib

:heavy_check_mark: test/yukicoder/1750.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1750"
#include "head.hpp"
#include "math/matrix.hpp"
#include "io/Scanner.hpp"
#include "io/Printer.hpp"

Scanner scanner;
Printer printer;

int main()
{
	int n, m;
	i64 T;
	scanner.scan(n, m, T);
	matrix<i64> a(n, n);
	for(int i = 1;i <= m;i++)
	{
		int s, t;
		scanner.scan(s, t);
		s++, t++;
		a.m[s][t] = a.m[t][s] = 1;
	}
	a = a.pow(T);
	printer.println(a.m[1][1]);
}
#line 1 "test/yukicoder/1750.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1750"
#line 1 "head.hpp"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ioclear std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
#define endl '\n'
#define CLOCK 1e3 * clock() / CLOCKS_PER_SEC


#line 2 "math/matrix.hpp"

using i64 = long long;
constexpr i64 P = 998244353;
constexpr int mmax = 2000;

template<typename T>
struct matrix
{
	int row, col;
	i64 m[mmax][mmax];

	matrix(int r, int c): row(r), col(c) {memset(m, 0, sizeof(m));}
	matrix(int r, int c, int val): row(r), col(c)
	{
		memset(m, 0, sizeof(m));
		for(int i = 1;i <= row;i++)
			for(int j = 1;j <= col;j++)
				m[i][j] = val;
	}
    matrix(int r, int c, std::vector<std::vector<T>> _m): row(r), col(c)
    {
    	memset(m, 0, sizeof(m));
		for(int i = 1;i <= row;i++)
			for(int j = 1;j <= col;j++)
				m[i][j] = _m[i][j];
    }

	matrix operator *= (const matrix &rhs)
	{
	 	assert(col == rhs.row);
	 	i64 tmp[mmax][mmax];
	 	memset(tmp, 0, sizeof(tmp));
	 	for(int k = 1;k <= col;k++)
	 		for(int i = 1;i <= row;i++)
	 			for(int j = 1;j <= rhs.col;j++)
	 				tmp[i][j] = (tmp[i][j] + ((m[i][k] * rhs.m[k][j]))) % P;
	 	memcpy(m, tmp, sizeof(tmp));
	 	return *this;
	}
	friend matrix operator *(const matrix &lhs, const matrix &rhs)
	{
		assert(lhs.col == rhs.row);
        matrix res = lhs;
        res *= rhs;
        return res;
	}
	matrix<T> pow(T k)
	{
		assert(row == col);
	    k--;
		matrix<T> Ans = *this, f = *this;
		while(k)
		{
			if(k & 1)
				Ans *= f;
			f *= f;
			k >>= 1;
		}
		return Ans;
	}
};
#line 2 "io/Scanner.hpp"

class Scanner
{
public:
	Scanner(std::FILE *f = stdin, std::size_t enough_buffer_size = 1 << 25)
		: f_(f), buffer_(new char[enough_buffer_size + 32]), buffer_head_(buffer_),
		  buffer_tail_(buffer_ + std::fread(buffer_, sizeof(char), enough_buffer_size + 32, f_)) {*buffer_tail_ = '\0';}
	~Scanner() {delete[] buffer_;}
	
	template<typename T>
	std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, bool>
	scan(T &x)
	{
		x = 0;
		while(*buffer_head_ != '-' && std::isspace(*buffer_head_))
			++buffer_head_;
		bool is_neg = *buffer_head_ == '-' && ++buffer_head_;
		char *old_buffer_head = buffer_head_;
		if(is_neg)
			while(std::isdigit(*buffer_head_)) x = x * 10 - (*buffer_head_++ - '0');
		else
			while(std::isdigit(*buffer_head_)) x = x * 10 + (*buffer_head_++ - '0');
		return buffer_head_ != old_buffer_head;
	}  

	template<typename... T>
	bool scan(T &...x)
	{
		return (... && scan(x));
	}

private:
	std::FILE *f_;
	char *buffer_, *buffer_head_, *buffer_tail_;
};
#line 2 "io/Printer.hpp"

class Printer
{
public:
	Printer(std::FILE *f = stdout, std::size_t buffer_size = 100000)
		: f_(f), buffer_(new char[buffer_size + 32]), buffer_head_(buffer_),
		  buffer_end_(buffer_ + buffer_size + 32), stk_(new char[32]), top_(stk_) {}
	~Printer()
	{
		flush();
		delete[] stk_;
		delete[] buffer_;
	}

	void flush()
	{
		std::fwrite(buffer_, buffer_head_ - buffer_, sizeof(char), f_);
		buffer_head_ = buffer_;
	}

	void putchar(char x)
	{
		if(buffer_end_ == buffer_head_)
			flush();
		*buffer_head_++ = x;
	}

	template<typename T>
	std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_signed_v<T>, void>
	print(T x)
	{
		if(x == 0)
			return this->putchar('0');
		if(x < 0)
		{
			putchar('-');
			do
			{
				T y = x / 10;
				*top_++ = y * 10 - x + '0';
				x = y;
			} while(x != 0);
		}
		else
		{
			do
			{
				T y = x / 10;
				*top_++ = x - y * 10 + '0';
				x = y;
			} while(x != 0);
		}
		if(buffer_end_ - buffer_head_ < top_ - stk_)
			flush();
		while(top_ != stk_) *buffer_head_++ = *--top_;
	}

	void print(char x) {return this->putchar(x);}

	template<typename T>
	std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char> && std::is_unsigned_v<T>, void>
	print(T x)
	{
		if(x == 0)
			return this->putchar('0');
		do
		{
			T y = x / 10;
			*top_++ = x - y * 10 + '0';
			x = y;
		} while(x != 0);
		if(buffer_end_ - buffer_head_ < top_ - stk_)
			flush();
		while(top_ != stk_) *buffer_head_++ = *--top_;
	}

	template<typename... T>
	void print(T... x)
	{
		return (..., print(x));
	}

	template<typename T>
	void println(T x)
	{
		return this->print(x), this->putchar('\n');
	}

private:
	std::FILE *f_;
	char *buffer_, *buffer_head_, *buffer_end_, *stk_, *top_;
};
#line 6 "test/yukicoder/1750.test.cpp"

Scanner scanner;
Printer printer;

int main()
{
	int n, m;
	i64 T;
	scanner.scan(n, m, T);
	matrix<i64> a(n, n);
	for(int i = 1;i <= m;i++)
	{
		int s, t;
		scanner.scan(s, t);
		s++, t++;
		a.m[s][t] = a.m[t][s] = 1;
	}
	a = a.pow(T);
	printer.println(a.m[1][1]);
}
Back to top page