結果
問題 | No.541 3 x N グリッド上のサイクルの個数 |
ユーザー |
|
提出日時 | 2017-06-30 23:54:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,884 bytes |
コンパイル時間 | 3,414 ms |
コンパイル使用メモリ | 220,792 KB |
最終ジャッジ日時 | 2025-01-05 00:57:06 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 61 |
コンパイルメッセージ
main.cpp: In function ‘void {anonymous}::toc()’: main.cpp:26:45: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 3 has type ‘std::chrono::duration<long int, std::ratio<1, 1000> >::rep’ {aka ‘long int’} [-Wformat=] 26 | void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); } | ~~~^ | | | long long int | %ld main.cpp: In member function ‘{anonymous}::MaiScanner& {anonymous}::MaiScanner::operator>>(std::string&)’: main.cpp:72:9: warning: no return statement in function returning non-void [-Wreturn-type] 72 | } | ^
ソースコード
#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl; #define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;} #define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl; #define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;} #define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;} #define ALL(v) (v).begin(),(v).end() #define repeat(l) for(auto cnt=0;cnt<(l);++cnt) #define iterate(b,e) for(auto cnt=(b);cnt!=(e);++cnt) #define MD 1000000007ll #define PI 3.1415926535897932384626433832795 template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count()) namespace { std::chrono::system_clock::time_point ttt; void tic() { ttt = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } #ifdef __MAI #define getchar_unlocked getchar #define putchar_unlocked putchar #endif #ifdef __VSCC #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #endif namespace { #define isvisiablechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template<typename T> void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'<cc; cc = getchar_unlocked()) if (cc == '-') sign = -1; for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked()) var = (var << 3) + (var << 1) + cc - '0'; var = var*sign; } inline int c() { return getchar_unlocked(); } inline MaiScanner& operator>>(int& var) { input_integer<int>(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer<long long>(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiablechar(cc); cc = getchar_unlocked()); for (; isvisiablechar(cc); cc = getchar_unlocked()) var.push_back(cc); } }; } MaiScanner scanner; // ----------------------------------------------------------------------- // ここから! // ----------------------------------------------------------------------- class llmod { public: const ll MOD = MD; private: ll val; inline ll cut(ll v) const { return ((v%MOD) + MOD) % MOD; } public: llmod() : MOD(MD), val(0) {} llmod(ll num, ll m = MD) : MOD(m), val(cut(num)) {} llmod(const llmod& lm, ll m) : MOD(m), val(lm.val) {} inline ll operator*() const { return val; } inline llmod& operator=(const llmod& lm) { val = lm.val; return *this; } inline llmod& operator=(ll v) { val = cut(v); return *this; } inline llmod& operator+=(ll v) { val = cut(val + v); return *this; } inline llmod& operator+=(const llmod& l) { val = cut(val + l.val); return *this; } inline llmod& operator-=(ll v) { val = cut(val - v); return *this; } inline llmod& operator-=(const llmod& l) { val = cut(val - l.val); return *this; } inline llmod& operator*=(ll v) { val = cut(val * v); return *this; } inline llmod& operator*=(const llmod& l) { val = cut(val * l.val); return *this; } inline llmod& operator++() { val = (val + 1) % MOD; return *this; } inline llmod operator++(int) { llmod t = *this; val = (val + 1) % MOD; return t; } }; ostream& operator<<(ostream& os, const llmod& l) { os << *l; return os; } inline llmod operator+(llmod t, const llmod& r) { return t += r; } inline llmod operator-(llmod t, const llmod& r) { return t -= r; } inline llmod operator*(llmod t, const llmod& r) { return t *= r; } // MEMO : 逆元...powm(n,MD-2) llmod pow(llmod x, ll p) { llmod y = 1; while (0 < p) { if (p % 2) y *= x; x *= x; p /= 2; } return y; } inline llmod& operator/=(llmod& l, const llmod& r) { return l *= pow(r, r.MOD - 2); } template<typename T> //typedef double T; class matrix { public: size_t height, width; valarray<T> data; matrix(size_t height, size_t width) :height(height), width(width), data(height*width) {} matrix(size_t height, size_t width, const valarray<T>& data) :height(height), width(width), data(data) {} inline T& operator()(size_t y, size_t x) { return data[y*width + x]; } inline T operator() (size_t y, size_t x) const { return data[y*width + x]; } inline T& at(size_t y, size_t x) { return data[y*width + x]; } inline T at(size_t y, size_t x) const { return data[y*width + x]; } inline void resize(size_t h, size_t w) { height = h; width = w; data.resize(h*w); } inline void fill(T val) { data = val; } matrix<T>& setDiag(T val) { for (size_t i = 0, en = min(width, height); i < en; ++i)at(i, i) = val; return *this; } inline bool issquare() const { return height == width; } void print(ostream& os) { os << "- - -" << endl; // << setprecision(3) for (size_t y = 0; y < height; ++y) { for (size_t x = 0; x < width; ++x) { os << setw(7) << at(y, x) << ' '; }os << endl; } } template<typename MT> void copyto2d(MT& d2) { for (size_t i = 0; i < width*height; ++i) { d2[i / width][i%width] = data[i]; } } // mathematics matrix<T> pow(long long) const; double det() const; T tr(); matrix<T>& transpose_self(); matrix<T> transpose() const; struct LU { size_t size; vector<int> pivot; vector<T> elem; }; }; // IO template<typename T> inline ostream& operator << (ostream& os, matrix<T> mat) { mat.print(os); return os; } // 掛け算 template<typename T> matrix<T> multiply(const matrix<T>& mat1, const matrix<T>& mat2) { assert(mat1.width == mat2.height); matrix<T> result(mat1.height, mat2.width); for (size_t i = 0, j, k; i < mat1.height; i++) { for (j = 0; j < mat2.width; j++) { for (k = 0; k < mat1.width; k++) { result(i, j) += mat1(i, k) * mat2(k, j); } } } return result; } template<typename T> valarray<T> multiply(const matrix<T>& mat1, const valarray<T>& vec2) { assert(mat1.width == vec2.size()); valarray<T> result(mat1.height); for (size_t i = 0, j; i < mat1.height; i++) { for (j = 0; j < mat1.width; j++) { result[i] += mat1(i, j) * vec2[j]; } } return result; } template<typename T> inline matrix<T>& operator*=(matrix<T>& mat1, matrix<T>& mat2) { mat1 = multiply(mat1, mat2); return mat1; } template<typename T> inline matrix<T> operator*(matrix<T>& mat1, matrix<T>& mat2) { return multiply(mat1, mat2); } // スカラー template<typename T> inline matrix<T>& operator+=(matrix<T>& mat, T val) { mat.data += val; return mat; } template<typename T> inline matrix<T>& operator*=(matrix<T>& mat, T val) { mat.data *= val; return mat; } template<typename T> inline matrix<T>& operator/=(matrix<T>& mat, T val) { mat.data /= val; return mat; } template<typename T> inline matrix<T>& operator^=(matrix<T>& mat, T val) { mat.data ^= val; return mat; } // 行列 template<typename T> inline matrix<T>& operator+=(matrix<T>& mat1, matrix<T>& mat2) { mat1.data += mat2.data; return mat1; } template<typename T> inline matrix<T> operator+(matrix<T>& mat1, matrix<T>& mat2) { return matrix<T>(mat1.height, mat1.width, mat1.data + mat2.data); } // べきじょう template<typename T> matrix<T> matrix<T>::pow(long long p) const { assert(issquare()); matrix<T> a = *this; matrix<T> b(height, height); b.setDiag(1); while (0 < p) { if (p % 2) { b *= a; } a *= a; p /= 2; } return b; } int main() { ll n; cin >> n; matrix<llmod> matz(6, 6, valarray<llmod>{ 3,0,0,1,0,1, 0,3,0,1,1,1, 0,0,3,0,1,1, 1,1,0,3,1,1, 0,1,1,1,3,1, 1,1,1,1,1,3 }); matrix<llmod> matAp = matz.pow(n - 1); valarray<llmod> stat = { 1,1,1,1,1,1 }; stat = multiply(matAp, stat); cout << *(stat.sum()) << endl; return 0; }