#858570 (C++17) No.727 仲介人moko

提出ソース

結果

問題	No.727 仲介人moko
ユーザー	snrnsidy
提出日時	2023-04-11 23:57:04
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	8,284 bytes
コンパイル時間	4,068 ms
コンパイル使用メモリ	374,612 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-04-16 19:00:26
合計ジャッジ時間	5,243 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-

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

コンパイルメッセージ

main.cpp: In function 'std::vector<int> berlekamp_massey(std::vector<int>)':
main.cpp:81:32: warning: 'lf' may be used uninitialized [-Wmaybe-uninitialized]
   81 |                 vector<int> c(i-lf-1);
      |                               ~^~~
main.cpp:67:13: note: 'lf' was declared here
   67 |         int lf, ld;
      |             ^~
main.cpp:80:44: warning: 'ld' may be used uninitialized [-Wmaybe-uninitialized]
   80 |                 lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
      |                                        ~~~~^~~~~~~~~~~~~
main.cpp:67:17: note: 'ld' was declared here
   67 |         int lf, ld;
      |                 ^~

ソースコード

raw source code

#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")	
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma") 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 
//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

const long long int mod = 1e9 + 7;
using lint = long long;
lint ipow(lint x, lint p){
	lint ret = 1, piv = x;
	while(p){
		if(p & 1) ret = ret * piv % mod;
		piv = piv * piv % mod;
		p >>= 1;
	}
	return ret;
}
vector<int> berlekamp_massey(vector<int> x){
	vector<int> ls, cur;
	int lf, ld;
	for(int i=0; i<x.size(); i++){
		lint t = 0;
		for(int j=0; j<cur.size(); j++){
			t = (t + 1ll * x[i-j-1] * cur[j]) % mod;
		}
		if((t - x[i]) % mod == 0) continue;
		if(cur.empty()){
			cur.resize(i+1);
			lf = i;
			ld = (t - x[i]) % mod;
			continue;
		}
		lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
		vector<int> c(i-lf-1);
		c.push_back(k);
		for(auto &j : ls) c.push_back(-j * k % mod);
		if(c.size() < cur.size()) c.resize(cur.size());
		for(int j=0; j<cur.size(); j++){
			c[j] = (c[j] + cur[j]) % mod;
		}
		if(i-lf+(int)ls.size()>=(int)cur.size()){
			tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod);
		}
		cur = c;
	}
	for(auto &i : cur) i = (i % mod + mod) % mod;
	return cur;
}
int get_nth(vector<int> rec, vector<int> dp, lint n){
	int m = rec.size();
	vector<int> s(m), t(m);
	s[0] = 1;
	if(m != 1) t[1] = 1;
	else t[0] = rec[0];
	auto mul = [&rec](vector<int> v, vector<int> w){
		int m = v.size();
		vector<int> t(2 * m);
		for(int j=0; j<m; j++){
			for(int k=0; k<m; k++){
				t[j+k] += 1ll * v[j] * w[k] % mod;
				if(t[j+k] >= mod) t[j+k] -= mod;
			}
		}
		for(int j=2*m-1; j>=m; j--){
			for(int k=1; k<=m; k++){
				t[j-k] += 1ll * t[j] * rec[k-1] % mod;
				if(t[j-k] >= mod) t[j-k] -= mod;
			}
		}
		t.resize(m);
		return t;
	};
	while(n){
		if(n & 1) s = mul(s, t);
		t = mul(t, t);
		n >>= 1;
	}
	lint ret = 0;
	for(int i=0; i<m; i++) ret += 1ll * s[i] * dp[i] % mod;
	return ret % mod;
}
int guess_nth_term(vector<int> x, lint n){
	if(n < x.size()) return x[n];
	vector<int> v = berlekamp_massey(x);
	if(v.empty()) return 0;
	return get_nth(v, x, n);
}
struct elem{int x, y, v;}; // A_(x, y) <- v, 0-based. no duplicate please..
vector<int> get_min_poly(int n, vector<elem> M){
	// smallest poly P such that A^i = sum_{j < i} {A^j \times P_j}
	vector<int> rnd1, rnd2;
	mt19937 rng(0x14004);
	auto randint = [&rng](int lb, int ub){
		return uniform_int_distribution<int>(lb, ub)(rng);
	};
	for(int i=0; i<n; i++){
		rnd1.push_back(randint(1, mod - 1));
		rnd2.push_back(randint(1, mod - 1));
	}
	vector<int> gobs;
	for(int i=0; i<2*n+2; i++){
		int tmp = 0;
		for(int j=0; j<n; j++){
			tmp += 1ll * rnd2[j] * rnd1[j] % mod;
			if(tmp >= mod) tmp -= mod;
		}
		gobs.push_back(tmp);
		vector<int> nxt(n);
		for(auto &i : M){
			nxt[i.x] += 1ll * i.v * rnd1[i.y] % mod;
			if(nxt[i.x] >= mod) nxt[i.x] -= mod;
		}
		rnd1 = nxt;
	}
	auto sol = berlekamp_massey(gobs);
	reverse(sol.begin(), sol.end());
	return sol;
}
lint det(int n, vector<elem> M){
	vector<int> rnd;
	mt19937 rng(0x14004);
	auto randint = [&rng](int lb, int ub){
		return uniform_int_distribution<int>(lb, ub)(rng);
	};
	for(int i=0; i<n; i++) rnd.push_back(randint(1, mod - 1));
	for(auto &i : M){
		i.v = 1ll * i.v * rnd[i.y] % mod;
	}
	auto sol = get_min_poly(n, M)[0];
	if(n % 2 == 0) sol = mod - sol;
	for(auto &i : rnd) sol = 1ll * sol * ipow(i, mod - 2) % mod;
	return sol;
}

vector <int> v = {0,1,12,486,42720,6615000,599484313,291848814,940887432,359615350,678345397,322826110,535714982,742062744,275016949,548819915,964501078,794648746,828747937,69089868,741116640,75830509,727542734,812134260,286524125,676582511,902705458,963000930,895570778,48289307,436587873,371570836,78861901,393155986,146890024,155968224,760007060,802173869,564913985,544330500,593163214,614684977,41806771,184940152,354253130,688089745,415553708,506060624,838728450,347359094,880366393,38445594,145839250,532951651,339768096,705417752,752436057,722273969,707711155,291281728,678851651,306869667,528543445,608449438,637758609,511419998,189522127,539198238,976511058,137637644,567893827,712292474,483724407,144030241,352906962,286436655,415790448,889377652,708543672,698972882,2227249,375311698,12706004,319374486,445060133,858976976,903048927,381444308,28964427,200595163,378622939,430073785,776494743,569865690,324028448,30735347,818180383,29846318,171353031,306151317,349657766,203277272,257603204,445394158,961031134,835876250,453364929,40963429,900873690,676838279,750343392,60732353,808972607,418199935,611315700,201220971,595948166,3021017,219229404,310042865,837967183,799799714,908933542,360629668,178207868,938048519,359242276,267360807,775282082,303462357,21259614,830306424,957699545,617048678,567659329,915387921,516356820,941695836,441091405,825869132,249684244,541630976,680954659,715006344,780441213,945062457,311238792,275888330,869088070,13485483,554277149,528097697,289344106,242071659,343715588,894667025,435282364,861765961,545885648,219126178,443319492,810678130,87810324,295692167,677616530,520705385,958336952,538207320,102651757,921505468,987657682,899543047,554802955,260789336,147235238,518184547,458687170,834132193,85842407,132474347,18443298,20712898,776024629,318144571,135032292,169104531,338621454,568160907,773773637,611343724,941675529,421663599,46494321,352953009,859275842,28445453,795571755,277478322,36491572,308951601,42877477,45478378,835603395,911173515,779732381,460227823,704718755,890758157,263769275,24367956,56800872,759406886,707041024,441883162,847588722,407069185,964381663,991495584,978180546,823630043,472812875,46508032,908711620,114842792,241953541,899682386,468656526,704901940,860798688,285737460,694265118,600701486,761800699,983662100,210014373,853030700,479360400,836064310,222627469,288868756,148089720,629542596,651176402,505889923,277863369,874618228,235127684,56214717,150865256,900218392,525917753,98433561,89421797,9759576,3785752,890905346,408916885,571587478,1240723,788862015,684915086,452585634,683514363,42516154,504763805,702281540,519713335,662196321,535523230,625351283,198271669,461933891,281194101,87361923,657513132,737855012,86361732,177296649,798695354,538933444,859771287,862394526,733813024,158472875,468130323,619736582,759819904,468126957,903923107,515557302,881517997,201340780,597288151,572042172,176699155,598756729,28679134,925416910,221296507,726048467,826282086};

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

	int n;

	cin >> n;

	cout << guess_nth_term(v,n) << '\n';

    return 0;   
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード