# 題解

### [atcoder ABC 363F - Palindromic Expression](https://atcoder.jp/contests/abc363/tasks/abc363_f)

注意到如果要分解出兩個數字塞在前後
其中一個數字一定會 $\le \sqrt{n}$

那可以用遞迴的方式
`dfs(n) = i*dfs(n/(i*j))*j`
其中 $j=rev(i)$
且 $i$ 跟 $j$ 都不包含 $0$

那要怎麼證複雜度是好的?
首先要記憶化遞迴結果
~~然後丟上去就發現過了呵呵~~

我猜複雜度是好的
我也不會證明

code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#pragma GCC optimize("Ofast")

inline bool ip(int n)
{
	string str=to_string(n);
	int l=0, r=str.size()-1;
	while(l<r)
	{
		if(str[l]!=str[r]) return false;
		l++, r--;
	}
	return true;
}

inline int rev(int n)
{
	string str=to_string(n);
	reverse(str.begin(), str.end());
	return stoll(str);	
}

inline bool hz(string str)
{
	for(auto& e : str)
	{
		if(e=='0')
		{
			return true;
		}
	}
	return false;
}

map<int, string> ms;
string dfs(int n)
{
	if(ms.count(n)) return ms[n];
	if(ip(n) && !hz(to_string(n))) return to_string(n);
	for(int i=2;i*i<=n;i++)
	{
		if(hz(to_string(i))) continue;
		int j=rev(i);
		if(n%(i*j)==0)
		{
			string next=dfs(n/(i*j));
			ms[n/(i*j)]=next;
			if(next!="-1" && !hz(next))
			{
				return (string)(to_string(i) + "*" + next + "*" + to_string(j));
			}
		}
	}
	return "-1";
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	cout << dfs(n);
}

### [atcoder ABC 377F - Avoid Queen Attack](https://atcoder.jp/contests/abc377/tasks/abc377_f)
注意到$M$很小所以可以$M^2$取交點

依舊實作地獄QAO

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#pragma GCC optimize("Ofast")

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, ans, a, b;
	cin >> n >> m;
	ans=n*n;
	set<int> rs, cs, ds1, ds2;
	while(m--)
	{
		cin >> a >> b;
		
		ans-=n;
		if(rs.count(a)) ans+=n;
		else
		{
			set<int> tmp;
			for(auto& e : cs) tmp.insert(e);
			for(auto& e : ds1) if(e-a>0 && e-a<=n) tmp.insert(e-a);
			for(auto& e : ds2) if(a-e>0 && a-e<=n) tmp.insert(a-e);
			ans+=tmp.size();
		}
		rs.insert(a);
		ans-=n;
		if(cs.count(b)) ans+=n;
		else
		{
			set<int> tmp;
			for(auto& e : rs) tmp.insert(e);
			for(auto& e : ds1) if(e-b>0 && e-b<=n) tmp.insert(e-b);
			for(auto& e : ds2) if(b+e>0 && b+e<=n) tmp.insert(b+e);
			ans+=tmp.size();
		}
		cs.insert(b);
		int mx=a+b-1;
		if(mx>n) mx=2*n+1-a-b;
		ans-=mx;
		if(ds1.count(a+b)) ans+=mx;
		else
		{
			set<pair<int, int>> tmp;
			for(auto& e : rs) if(a+b-e>0 && a+b-e<=n) tmp.insert({e, a+b-e});
			for(auto& e : cs) if(a+b-e>0 && a+b-e<=n) tmp.insert({a+b-e, e});
			for(auto& e : ds2) if((e+a+b)%2==0 && (e+a+b)/2>0 && (e+a+b)/2<=n && a+b-(e+a+b)/2>0 && a+b-(e+a+b)/2<=n) tmp.insert({(e+a+b)/2, a+b-(e+a+b)/2}); 
			ans+=tmp.size();
		}
		ds1.insert(a+b);
		mx=n-abs(a-b);
		ans-=mx;
		if(ds2.count(a-b)) ans+=mx;
		else
		{
			set<pair<int, int>> tmp;
			for(auto& e : rs) if(e-a+b>0 && e-a+b<=n) tmp.insert({e, e-a+b});
			for(auto& e : cs) if(a-b+e>0 && a-b+e<=n) tmp.insert({a-b+e, e});
			for(auto& e : ds1) if((e+a-b)%2==0 && (e+a-b)/2>0 && (e+a-b)/2<=n && e-(e+a-b)/2>0 && e-(e+a-b)/2<=n) tmp.insert({(e+a-b)/2, e-(e+a-b)/2});
			ans+=tmp.size();
		}
		ds2.insert({a-b});
	}
	cout << ans;
}