#705774 (C++17) No.1706 Many Bus Stops (hard)

提出ソース

結果

問題	No.1706 Many Bus Stops (hard)
ユーザー	chocorusk
提出日時	2021-10-08 22:32:41
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 2,000 ms
コード長	5,257 bytes
コンパイル時間	3,796 ms
コンパイル使用メモリ	195,608 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-23 05:30:04
合計ジャッジ時間	5,146 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
template<typename T>
struct Matrix{
	vector<vector<T>> a;
	Matrix(){}
	Matrix(size_t n, size_t m):a(n, vector<T>(m, 0)){}
	Matrix(size_t n):Matrix(n, n){}
	Matrix(vector<vector<T>> a):a(a){}

	size_t height() const{
		return a.size();
	}
	size_t width() const{
		return a[0].size();
	}

	inline const vector<T> &operator[](size_t k) const{
		return a[k];
	}
	inline vector<T> &operator[](size_t k){
		return a[k];
	}

	static Matrix I(size_t n){
		Matrix mat(n);
		for(int i=0; i<n; i++) mat[i][i]=1;
		return mat;
	}

	Matrix &operator+=(const Matrix &b){
		size_t n=height(), m=width();
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				(*this)[i][j]+=b[i][j];
			}
		}
		return (*this);
	}
	Matrix &operator-=(const Matrix &b){
		size_t n=height(), m=width();
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				(*this)[i][j]-=b[i][j];
			}
		}
		return (*this);
	}
	Matrix &operator*=(const Matrix &b){
		size_t n=height(), m=width(), l=b.width();
		vector<vector<T>> c(n, vector<T>(l, 0));
		for(int i=0; i<n; i++){
			for(int j=0; j<l; j++){
				for(int k=0; k<m; k++){
					c[i][j]+=(*this)[i][k]*b[k][j];
				}
			}
		}
		a.swap(c);
		return (*this);
	}
	Matrix operator+(const Matrix &b) const{
		return (Matrix(*this)+=b);
	}
	Matrix operator-(const Matrix &b) const{
		return (Matrix(*this)-=b);
	}
	Matrix operator*(const Matrix &b) const{
		return (Matrix(*this)*=b);
	}

	Matrix pow(ll k) const{
		Matrix ap(a), ret=I(height());
		while(k){
			if(k&1) ret*=ap;
			ap*=ap;
			k>>=1;
		}
		return ret;
	}

	static pair<Matrix, Matrix> Gauss_Jordan(const Matrix &a, const Matrix &b){
		size_t n=a.height(), m=a.width(), l=b.width();
		Matrix c(n, m+l);
		for(int i=0; i<n; i++) for(int j=0; j<m; j++) c[i][j]=a[i][j];
		for(int i=0; i<n; i++) for(int j=0; j<l; j++) c[i][j+m]=b[i][j];
		int d=0;
		for(int i=0; i<m; i++){
			int p=-1; 
			for(int j=d; j<n; j++){
				if(c[j][i]!=0){
					p=j; break;
				}
			}
			if(p==-1) continue;
			swap(c[p], c[d]);
			T invc=T(1)/c[d][i];
			for(int j=i; j<m+l; j++) c[d][j]*=invc;
			for(int j=0; j<n; j++){
				if(j==d) continue;
				T c0=c[j][i];
				for(int k=i; k<m+l; k++){
					c[j][k]-=c0*c[d][k];
				}
			}
			d++;
		}
		Matrix reta(n, m), retb(n, l);
		for(int i=0; i<n; i++) for(int j=0; j<m; j++) reta[i][j]=c[i][j];
		for(int i=0; i<n; i++) for(int j=0; j<l; j++) retb[i][j]=c[i][j+m];
		return make_pair(reta, retb);
	}

	static pair<vector<T>, vector<vector<T>>> linear_equations(const Matrix &a, const vector<T> &b){
		int n=a.height(), m=a.width();
		Matrix B(n, 1);
		for(int i=0; i<n; i++) B[i][0]=b[i];
		auto p=Gauss_Jordan(a, B);
		vector<int> myon(n,-1);
		vector<int> nuo(m, -1);
		for(int i=0; i<n; i++){
			bool allzero=1;
			for(int j=0; j<m; j++){
				if(p.first[i][j]!=0){
					allzero=0;
					myon[i]=j;
					nuo[j]=i;
					break;
				}
			}
			if(allzero && p.second[i][0]!=0){
				vector<T> retc;
				vector<vector<T>> retd;
				return make_pair(retc, retd);
			}
		}
		vector<T> c(m);
		vector<vector<T>> d;
		for(int i=0; i<m; i++){
			if(nuo[i]==-1){
				vector<T> v(m);
				v[i]=1;
				for(int j=0; j<n; j++){
					if(myon[j]!=-1) v[myon[j]]=-p.first[j][i];
				}
				d.push_back(v);
			}else{
				c[i]=p.second[nuo[i]][0];
			}
		}
		return make_pair(c, d);
	}

	Matrix inv() const{
		int n=height();
		Matrix b=I(n);
		auto p=Gauss_Jordan(*this, b);
		if(p.first[n-1][n-1]==0){
			Matrix ret(0);
			return ret;
		}
		return p.second;
	}

	int rank() const{
		int n=height(), m=width();
		Matrix b(n, 0);
		auto p=Gauss_Jordan(*this, b);
		for(int i=0; i<n; i++){
			bool allzero=1;
			for(int j=0; j<m; j++){
				if(p.first[i][j]!=0){
					allzero=0;
					break;
				}
			}
			if(allzero) return i;
		}
		return n;
	}

	T det() const{
		size_t n=height();
		Matrix A(a);
		T ret(1);
		for(int i=0; i<n; i++){
			int p=-1; 
			for(int j=i; j<n; j++){
				if(A[j][i]!=0){
					p=j; break;
				}
			}
			if(p==-1){
				return 0;
			}
			if(p!=i) ret*=(-1);
			swap(A[p], A[i]);
			ret*=A[i][i];
			T inva=T(1)/A[i][i];
			for(int j=i+1; j<n; j++){
				T a0=A[j][i];
				for(int k=i; k<n; k++){
					A[j][k]-=inva*a0*A[i][k];
				}
			}
		}
		return ret;
	}
};
using mint=modint1000000007;
using Mat=Matrix<mint>;
int main()
{
    // int t; cin>>t;
    // while(t--){
    ll c, n, m;
    cin>>c>>n>>m;
    //ll c=3, n, m=1;
    //cin>>n;
    Mat mat(4);
    mint x0=mint(c).inv(), x1=mint(c-1).inv();
    mat[0][0]=x0, mat[0][2]=x0*(c-1), mat[1][1]=x0, mat[1][3]=x0*(c-1), mat[2][1]=1, mat[3][0]=x1, mat[3][1]=x1*(c-2);
    mat=mat.pow(n);
    mint p=mat[0][1]+mat[0][2]+mat[0][3];
    mint ans=1-(p.pow(m));
    cout<<ans.val()<<endl;
    //}
    return 0;
}

yukicoder

結果

テストケース

ソースコード