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

提出ソース

結果

問題	No.727 仲介人moko
ユーザー	snrnsidy
提出日時	2023-04-12 00:14:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	8,357 bytes
コンパイル時間	4,329 ms
コンパイル使用メモリ	376,268 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-07 20:04:53
合計ジャッジ時間	5,087 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
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:83:44: warning: 'ld' may be used uninitialized [-Wmaybe-uninitialized]
   83 |                 lint k = -(x[i] - t) * ipow(ld, mod - 2) % mod;
      |                                        ~~~~^~~~~~~~~~~~~
main.cpp:70:17: note: 'ld' was declared here
   70 |         int lf, ld;
      |                 ^~
main.cpp:84:32: warning: 'lf' may be used uninitialized [-Wmaybe-uninitialized]
   84 |                 vector<int> c(i-lf-1);
      |                               ~^~~
main.cpp:70:13: note: 'lf' was declared here
   70 |         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;
long long int dp[601][301][301];

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 = {1,12,540,60480,13608000,388767965,645191976,384292627,170943676,792982132,967583314,635913540,734687698,967270607,440666498,129303649,168891882,233928475,582618707,851765584,773416504,344168576,932894336,315287407,676771790,384068716,262876219,222483935,212317440,55985082,901468955,564817875,633002015,271722591,351843506,231821471,542185158,652200374,750667077,317868612,307775565,35707346,944994813,365229047,404534814,605099319,787927240,513083973,717223316,769467416,858235643,923730020,548841757,213086369,902526712,936141197,68237145,221729914,493552043,693741141,702878531,401672869,950737672,127611062,218579693,440821645,830623563,449337564,569430367,20248827,481403143,924245533,139577582,44551212,484296127,455905615,848979279,434078352,27211342,261425370,106330727,751944951,540644367,366683701,962879422,2549769,761846687,622995222,886048631,901094133,843828215,639002975,288036253,514660479,239397192,340651352,389866617,397874322,541917136,93091095,72942977,441661332,932869732,222791293,263519398,730327558,792591425,58044597,243912126,738163006,299650828,851106824,165905843,496761497,602170747,997944756,700937105,322699752,23991847,340057210,395998815,256052009,650175864,691676420,552725129,85731217,973696370,509674225,600745631,683043439,885777664,746198366,243001034,185101512,783765552,965593726,384985775,988139044,110928282,213042600,472167375,555847833,693373618,234512387,18724425,783587278,449929855,725105286,515514474,599558139,34525243,376232558,506014282,830767626,351155120,102495508,880569234,14164961,87361364,837975611,177079193,17665247,81883709,560544166,73320494,860630478,36564737,48504433,929109682,401804140,778444113,233880451,749298224,246245236,844599207,3366449,20433903,861232608,106516007,578348543,810937741,60781817,623171490,431115480,136695024,477381312,24462493,879952425,193230119,146639815,47409420,424265457,600409974,464211218,630505662,588660016,415603557,85157026,435118894,499628521,185984647,745675433,174875879,253514869,578715235,771166665,441476213,99395703,431370401,76842167,929178001,756893068,578729147,887618229,357426680,697164694,223902623,458720545,110371437,128385304,765647899,520048266,617303224,438721491,621554984,505391754,173835066,113497816,89726940,787583324,624036753,282718331,344362085,720723520,417178181,384781390,656732501,874966054,291065054,209667393,740210390,911655415,8401680,577068574,505909428,832694506,369143910,306448042,204763580,106547552,740558461,361606953,142739925,530976331,461928219,977269969,13821949,766499786,612712134,443633141,885974774,575465997,815627634,136567297,894922038,840342033,97042672,161341858,802392520,306912577,827635390,511969702,361027723,876792366,795814332,623673167,406958752,983021558,972277788,127498201,197444700,415856428,754358633,553653572,799345760,921875175,189355460,19471756,400900827,643205332,66274064,592197491,798654514,139170502,269693009,704082588,398097207,353160983,57642915,525897297};
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

	int n;

	cin >> n;

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

    return 0;   
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード