# 2021 5 月 Ten Point Round #10 (Div.1 + Div.2) 題解

Hope you enjoyed the round!

<!---## Div.2--->

## pA 揮霍的土豪觀光客 (Splurge wealthy tourist)

**Prepared By Colten**

本題我們可以先計算如果繞完一整圈，會需要多少花費。

確定好一圈的總花費之後，我們就可以將此總花費除以 Jack 的預算。

不過假如預算無法被一圈的總花費整除，那麼代表勢必至少要再多跑一圈，才能確保將所有花費花光。

時間複雜度：$O(1)$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int a,b,c,d,e;
	
	cin >> a >> b >> c >> d >> e;
	
	int input;
	
	cin >> input;
	
	cout << input / ( a + b + c + d + e ) + ( input % ( a + b + c + d + e ) != 0 ) << "\n";
	
	return 0;
} 

:::

## pB Gunjyo 與樹枝 (Gunjyo and branches)

**Prepared By Colten**

由於樹枝是可以被折斷的，因此我們可以很貪心的先將所有樹枝都先做一次排序，接著我們就可以每次都取目前可用的樹枝當中，樹枝長度第 $4$ 長的樹枝，並將第 $3,2,1$ 長的樹枝通通折斷成跟第 $4$ 長的樹枝的長度一樣，如此一來就可以很貪心的使所有的正方形都是大的。

時間複雜度：$O(N+NlogN)$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n;
	
	cin >> n;
	
	vector <int> a(n);
	
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
	}
	
	sort(a.begin(),a.end());
	
	int ans = 0;
	
	for(int i=n-4;i>=0;i-=4)
	{
		ans += a[i] * a[i];
	}
	
	cout << ans << "\n";
	
	return 0;
} 

:::

## pC 在島嶼圈養的動物 (Animals in captivity on the island)

**Prepared By Colten**

我們首先可以先觀察到題目的範圍 $1 \le n,m \le 50$，數值範圍特別小，因此本題主要是在考大家實作的細心與耐心程度，我們可以先利用一個迴圈先枚舉所有的可行的正方形邊長，接著利用此邊長開始在地圖上枚舉所有可能，直到找到其中一個正方形區域當中，都是陸地，沒有海水，則代表此區域是可以架設柵欄的，則輸出答案，特別注意的是：由於可能會有很多種答案，因此題目有說明最佳解的形式，所以在枚舉時要記得考量到這點，去做枚舉順序上的改變。

時間複雜度：$O(N^5)$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

int mp[105][105];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n,m;
	
	cin >> n >> m;
	
	for(int i=0;i<n;i++)
	{
		for(int k=0;k<m;k++)
		{
			cin >> mp[i][k];
		}
	}
	
	for(int u=min(n,m);u>=3;u--)
	{
		for(int i=0;i<n;i++)
		{
			for(int k=0;k<m;k++)
			{
				if( i + u > n || k + u > m ) continue;
				
				bool square_check = true;
				
				for(int t1=i;t1<i+u;t1++)
				{
					for(int t2=k;t2<k+u;t2++)
					{
						if( mp[t1][t2] == 0 )
						{
							square_check = false;
							
							break;
						}
						
						if( square_check == false ) break;
					}
				}
				
				if( square_check == true )
				{	
					for(int t1=i;t1<i+u;t1++)
					{
						if( t1 != i && t1 != i + u - 1 )
						{
							mp[t1][k] = 2;
							
							mp[t1][k+u-1] = 2;
							
							continue;
						}
						
						for(int t2=k;t2<k+u;t2++)
						{
							mp[t1][t2] = 2;
						}
					}
					
					cout << "YES\n";
					
					for(int t1=0;t1<n;t1++)
					{
						for(int t2=0;t2<m;t2++)
						{
							cout << mp[t1][t2];
							
							if( t2 != m - 1 ) cout << " ";
						}
						
						cout << "\n";
					}
					
					exit(0);
				}
			}
		}
	}
	
	cout << "IMPOSSIBLE\n";
	
	return 0;
} 

:::

## pD 球與管子 (Tube of balls)
**Prepared By Fysty**

假設從左邊放入的球共 $l$ 顆，依序是編號 $x_1,x_2,...,x_l$.

因為沒有任何球放不下，所以隔板以左一定恰有 $l$ 顆球。

因此編號 $x_i$ 的球一定會停在空間 $i$.

從右邊放入的球作法類似，就只是相反而已。

以上可以用陣列實作，也可以用 stl::deque，左右端放入分別對應 push_front() 跟 push_back()。

每個子測資的時間複雜度為 $O(n)$.

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define F first
#define S second
const int MOD=1e9+7;
const ll INF=2e18;

int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        deque<ll> dq;
        rep(i,n)
        {
            ll a;
            char c;
            cin>>a>>c;
            if(c=='L') dq.push_front(a);
            else dq.push_back(a);
        }
        while(!dq.empty())
        {
            cout<<dq.front()<<" ";
            dq.pop_front();
        }
        cout<<"\n";
    }
}

:::

## pE 最高價值的交換 (Highest value exchange)
**Prepared By Colten**

我們可以先注意到的是，本題主要的操作如下：

- 我們必須要從一個序列當中，拿出最大值
- 我們必須要從一個序列當中，移除最大值
- 我們每新增一次的元素之後，就必須更新目前這個序列的最大值

綜合以上幾點，我們可以利用 STL-priority_queue 來幫我們有效率地完成這些操作。

當然也可以使用 STL-multiset 來完成這些操作，不過以下提供 priority_queue 的作法

時間複雜度：$O(N\log N)$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

priority_queue <int> pq1,pq2;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n;
	
	cin >> n;
	
	int ans1 = 0,ans2 = 0;
	
	while(n--)
	{
		int a,b,c;
		
		cin >> a >> b >> c;
		
		pq1.push(a);
		
		pq2.push(b);
		
		if( c == 1 )
		{
			int u1 = pq1.top(),u2 = pq2.top();
			
			ans1 += u2;
			
			ans2 += u1;
			
			pq1.pop();
			
			pq2.pop();
			
			pq1.push(u2);
			
			pq2.push(u1);
		}
	}
	
	cout << ans1 << " " << ans2 << "\n";
	
	return 0;
}

:::

## pF 多項式大師 (Master of Polynomials)
**Prepared By Fysty**

當我們除以 $a$ 的時候，要轉成乘以 $a^{-1}\bmod p$，$a^{-1}$ 為 $a$ 的模反元素，而由費馬小定理我們知道 $a^{-1}\equiv a^{-1}\cdot a^{p-1}\equiv a^{p-2}\pmod p$.

我們提供三種構造方法：

**Construction 1** (時間複雜度 $O(p^3)$)

將 $0,1,...,p-1$ 代入 $f(x)$ 會得到 $p$ 個 $p$ 元一次方程式。

所以我們可以用高斯消去法解出 $a_0,a_1,...,a_{p-1}$，注意除以一個數要看成乘以該數的模反元素。

這個方法的複雜度是 $O(p^3)$，只夠過前幾個子題。

**Construction 2** (時間複雜度 $O(p^2)$)

我們利用拉格朗日插值法。

令 $P(x)=x(x-1)(x-2)\cdots(x-p+1)$.

則 $f(x)=\sum_{k=0}^{p-1}\frac{\frac{P(x)}{x-k}}{\prod\limits_{l\neq k}(k-l)}$

若 $P(x)$ 的係數一開始先用 $O(p^2)$ 的 dp 求出。

則對於每個 $k$，$\frac{P(x)}{x-k}$ 的係數可以利用多項式除法在 $O(p\log p)$ 內算出。

令 $S_k=\prod\limits_{l\neq k}(k-l)$，則 $S_0=(-1)^{p-1}\cdot\prod\limits_{i=1}^{p-1} i$.

由 Wilson's Theorem 得 $S_0\equiv (-1)^p\pmod p$.

注意 $-1\equiv 1\pmod p$，所以 $S_0\equiv -1\pmod p$.

而 $\prod\limits_{l\neq k}(k-l)\equiv \prod\limits_{l\neq k-1}(k-1-l)\times \frac{k}{k-1-p}\equiv \prod\limits_{l\neq k-1}(k-1-l)\pmod p$

所以 $S_0\equiv S_1\equiv\cdots\equiv S_{p-1}\equiv -1\pmod p$.

最後用 $O(p^2)$ 將每一個部分加起來就得到 $f(x)$ 的係數了。

**Construction 3** (時間複雜度 $O(p^2)$)

我們再次利用費馬小定理。

考慮 $f_k(x)=r_k-r_k(x-k)^{p-1}$.

注意到當 $x\neq k$ 時，$f_k(x)\equiv r_k-r_k\equiv 0\pmod p$，而 $f_k(k)\equiv r_k\pmod p$.

因此所求 $f(x)=\sum\limits_{k=0}^{p-1} f_k(x)$.

而 $\binom{p-1}{0},\binom{p-1}{1},...,\binom{p-1}{p-1}$ 可以花 $O(p\log p)$ 事先求出。

所以每個 $f_k(x)$ 的係數可以在 $O(p)$ 內求出。

最後用 $O(p^2)$ 將全部加起來。

**Remark**

不難證明其實答案是唯一的。

:::spoiler 參考解法 (C++) (Constuction 2)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define F first
#define S second
const int MOD=1e9+7;
const ll INF=2e18;

int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll p;
        cin>>p;
        vector<ll> r(p),a(p,0),dp(p+1,0),tmp(p+1,0);
        rep(i,p) cin>>r[i];
        dp[0]=1;
        rep1(i,p)
        {
            rep1(j,i) tmp[j]=(tmp[j]+dp[j-1])%p;
            rep(j,i) tmp[j]=(tmp[j]+dp[j]*(p-i)%p)%p;
            rep(j,i+1) dp[j]=tmp[j],tmp[j]=0;
        }
        rep(i,p)
        {
            ll c=r[i]*(p-1)%p,cur=0;
            for(int j=p-1;j>=0;j--)
            {
                ll d=(dp[j+1]-cur+p)%p;
                a[j]=(a[j]+c*d%p)%p;
                cur=d*(p-i)%p;
            }
        }
        rep(i,p) cout<<a[i]<<" ";
        cout<<"\n";
    }
}

:::
:::spoiler 參考解法 (C++) (Constuction 3)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define F first
#define S second
const int MOD=1e9+7;
const ll INF=2e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll p;
        cin>>p;
        vector<ll> r(p),a(p,0),c(p,1);
        rep1(i,p-1) c[i]=c[i-1]*(p-i)%p*inv(i,p)%p;
        rep(i,p)
        {
            cin>>r[i];
            ll x=1;
            a[0]=(a[0]+r[i])%p;
            for(int j=p-1;j>=0;j--)
            {
                a[j]=(a[j]-c[j]*x%p*r[i]%p+p)%p;
                x=x*(p-i)%p;
            }
        }
        rep(i,p) cout<<a[i]<<" ";
        cout<<"\n";
    }
}

:::

## pG 多邊形 (Polygon)
**Prepared By LittleCube**
### 前言
這題並不是數學題，
仔細想想就會發現用排列組合列式極難，當然如果你夠電搞不好也是可行的。

感謝所有有撈分/AC的人><

### Subtask 1, 2, 3
這3個subtask是給暴搜/特判分的，基本上就直接DFS下去就好。

### Subtask 4
似乎不能再這樣暴搜下去了，所以有兩個觀察：

- 走過的線段必連續
- 實際上在哪個點不重要，重要的是左邊走了多少，右邊走了多少

所以，這樣改一下，可以列出狀態：
$dp[i][j][k] =$第 $i$ 步的時候，左邊長 $j$ 而右邊長 $k$，
這樣轉移就有一些case：

- 當 $j = 0$ 或 $k = 0$，可以多畫一條，
- 否則只有在畫過的移動這個選擇。

特別注意，當 $j + k = K$ ，表示走完了，可以開始閒晃，每走一步方法數$\times 2$。
複雜度$O(NK^2)$。
### Subtask 5
接下來可以做的事就是觀察這個DP，發現轉移可以用矩陣快速冪加速，
會是一個$k^2 + 1$的方陣，
所以複雜度$O(K^6\log N)$
但是這個矩陣其實有很多都沒辦法轉移或沒用到，
所以可以壓狀態，或是對稀疏的部分優化（800ms $\rightarrow$ 100ms）。

### Subtask 6
**Idea By dreamoon**
但有沒有發現，其實不能走到的情形比較好算？
令$F_k^{i..j}$表示從 $k$ 開始，從頭到尾都只走在 $i$ **向右走**到 $j$ 的所有邊上，

參考路線：$1 \rightarrow 2 \rightarrow 3 \rightarrow \cdots \rightarrow K - 2 \rightarrow K - 1 \rightarrow K \rightarrow 1 \rightarrow 2 \rightarrow \cdots$

所求 $= F_1^{1..K} + F_1^{K..K-1} + \dots + F_1^{2..1} - F_1^{1..K - 1} - F_1^{K..K - 2} - \cdots - F_1^{3..1}$

旋轉之後會得到：
所求 $= F_1^{1..K} + F_2^{1..K} + \dots + F_K^{1..K} - F_1^{1..K - 1} - F_2^{1..K - 1} - \cdots - F_{K - 1}^{1..K - 1}$

可以用兩次矩陣求得，
複雜度$O(K^3\log N)$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007
using namespace std;

ll k, n, tmpmat[105][105];

void copy(ll a[105][105], ll b[105][105])
{
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            b[i][j] = a[i][j];
}

void mul(ll a[105][105], ll b[105][105], ll c[105][105])
{
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            c[i][j] = 0;
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            for (int p = 0; p <= 100; p++)
                if (a[i][p] != 0)
                    if (b[p][j] != 0)
                        c[i][j] = (c[i][j] + a[i][p] * b[p][j]) % MOD;
}

void mtxfastpow(ll base[105][105], ll res[105][105], ll p)
{
    while (p > 0)
    {
        if (p & 1)
        {
            mul(res, base, tmpmat);
            copy(tmpmat, res);
        }
        p >>= 1;
        mul(base, base, tmpmat);
        copy(tmpmat, base);
    }
}

ll fastpow2(ll p)
{
    ll a = 1, b = 2;
    while (p > 0)
    {
        if (p & 1)
            a = a * b % MOD;
        p >>= 1;
        b = b * b % MOD;
    }
    return a;
}

ll cal(int k)
{
    ll base[105][105] = {{0}}, res[105][105] = {{0}}, ans = 0;
    base[1][2] = 1;
    base[k][k - 1] = 1;
    for (int i = 2; i < k; i++)
    {
        base[i][i + 1] = 1;
        base[i][i - 1] = 1;
    }
    for (int i = 0; i <= k; i++)
        res[i][i] = 1;
    mtxfastpow(base, res, n);
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            ans = (ans + res[i][j]) % MOD;
    return ans;
}

signed main()
{
    cin >> k >> n;
    cout << (fastpow2(n) - cal(k) + cal(k - 1) + MOD) % MOD << '\n';
}

:::

### 道歉啟事

抱歉官解壓了一點常數，以至於時限卡的有點緊，被卡常的對不起 ;w;

官解壓到常數的地方：
- 稀疏矩陣優化
- 把乘法開固定大小可以unroll-loops，常數相對較小

既然都壓常了，就順便講一下：

使用 C++ 作答的可以考慮選擇 GNU C++17 9.2.0 (64 bit, msys 2)，跑比較快
(例如這題的官解這樣跑快2倍)
然後真的覺得複雜度對的時候可以開 Ofast, unroll-loops 碰碰運氣
當然可以也砸一些怪怪的矩陣乘法優化，但是官解並沒有這麼毒瘤