結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー Ryan Shaw
提出日時 2026-04-18 02:44:41
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 3,735 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,966 ms
コンパイル使用メモリ 273,356 KB
実行使用メモリ 16,256 KB
最終ジャッジ日時 2026-04-18 02:44:46
合計ジャッジ時間 3,850 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:85:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                                                   ~~~~~~~~^
main.cpp:85:24: note: within this loop
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                       ~^~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream> 
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//

int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];

int expo(int a, int b){
	int res=1;
	a%=MOD;
	while (b){
		if (b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

int inv(int num){
	return expo(num, MOD-2);
}

void initfact(){
	fact[0]=1;
	for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
	invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
	for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
 
int ncr(int n, int r){
	if (n<r||r<0)return 0;
	return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}

int gcd(int a, int b){
	while (b){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}

int lcm(int a, int b){
	int temp=gcd(a, b);
	a/=temp;
	b/=temp;
	return a*b*temp;
}

void initcatalan(int k){
	cat[0]=1;
	for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}

const int smax=20000;

bitset<smax+1> dp[105][105];
int a[105]={
	0,0,
	1,3,33,16,64,152,120,144,112,84,60,129,156,4,132,168,76,68,
	24,188,136,36,8,92,160,184,31,124,128,35,177,185,147,167,193,
	187,73,27,55,126,41,146,25,29,83,189,191,155,79,171,174,173,
	70,71,197,172,198,176,151,159,183,170,130,162,80,175,165,186,
	199,133,182,169,180,181,190,103,93,166,161,111,98,86,122,178,
	157,179,148,143,113,154,127,135,141,149,153,139,138,163,150
};
int b[105]={
	0,0,0,
	15,48,192,121,105,104,119,195,137,200,40,96,196,49,12,51,28,
	9,116,20,140,72,56,52,17,32,19,5,45,23,7,13,21,6,11,2,18,
	194,14,100,10,37,43,39,26,22,34,53,44,47,57,30,46,38,54,61,
	63,58,42,62,59,69,50,67,89,65,75,66,74,81,77,87,85,78,82,
	91,101,88,95,94,90,97,99,107,106,115,109,114,110,102,108,117,
	134,125,118,142,123,158
};
int e1[105], e2[105], u[205], v[205], c[205], sq[150], sc;

vector<int> get(int l, int r, int s){
	if (l+1==r){
		if (s==a[r])return {e1[r]};
		vector<int> q=get(r-2, r-1, s-b[r]);
		reverse(q.begin(), q.end());
		q.pb(e2[r]);
		return q;
	}
	if (l==r-2){
		if (s==b[r])return {e2[r]};
		vector<int> q=get(l, r-1, s-a[r]);
		q.pb(e1[r]);
		return q;
	}
	if (s>=a[r]&&dp[l][r-1][s-a[r]]){
		vector<int> q=get(l, r-1, s-a[r]);
		q.pb(e1[r]);
		return q;
	}
	vector<int> q=get(l, r-2, s-b[r]);
	q.pb(e2[r]);
	return q;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while (t--){
		int n;
		cin>>n;
		for (int i=0; i*i<=smax; ++i)sq[sc++]=i*i;
		int m=0;
		u[++m]=1; v[m]=2; c[m]=a[2]; e1[2]=m;
		for (int i=3; i<=n; ++i){
			u[++m]=i-2; v[m]=i; c[m]=b[i]; e2[i]=m;
			u[++m]=i-1; v[m]=i; c[m]=a[i]; e1[i]=m;
		}
		cout<<m<<"\n";
		for (int i=1; i<=m; ++i)cout<<u[i]<<" "<<v[i]<<" "<<c[i]<<"\n";
		dp[1][2][a[2]]=1;
		for (int r=3; r<=n; ++r){
			for (int l=1; l<=r-3; ++l)dp[l][r]=(dp[l][r-2]<<b[r])|(dp[l][r-1]<<a[r]);
			dp[r-2][r][b[r]]=1;
			dp[r-2][r]|=dp[r-2][r-1]<<a[r];
			dp[r-1][r][a[r]]=1;
			dp[r-1][r]|=dp[r-2][r-1]<<b[r];
		}
		for (int l=1; l<=n; ++l){
			for (int r=l+1; r<=n; ++r){
				int s=0;
				while (!dp[l][r][sq[s]])++s;
				vector<int> q=get(l, r, sq[s]);
				cout<<q.size();
				for (int x:q)cout<<" "<<x;
				cout<<"\n";
			}
		}
	}
}
0