# Ten Point Round #9 (Div.1 + Div.2) 題解

希望大家喜歡這次的比賽 ><

## pA 三階行列式 - 計算 (Determinant Calculation)

**Prepare by Colten**

照著題目給予的公式做計算後輸出即可！但是使用 C++ 的人要小心 overflow 的問題

:::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 a1,a2,a3,b1,b2,b3,c1,c2,c3;
	
	cin >> a1 >> a2 >> a3;
	
	cin >> b1 >> b2 >> b3;
	
	cin >> c1 >> c2 >> c3;
	
	int ans = a1 * b2 * c3 + a2 * b3 * c1 + a3 * b1 *c2;
	
	ans -= a1 * b3 * c2;
	
	ans -= a2 * b1 * c3;
	
	ans -= a3 * b2 * c1;
	
	cout << ans << "\n";
	
	return 0;
}

:::

## pB 人生海海 (People Life Ocean Wild)

**Prepared by Colten**

利用迴圈針對每一個點 $i$ 去檢查是否有符合 $a[i-1] > a[i] < a[i+1]$，並利用一個變數去記錄答案。

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

#include <bits/stdc++.h>

#define int long long

using namespace std;

int a[1005];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q;
	
	cin >> q;
	
	while(q--)
	{
		int n;
		
		cin >> n;
		
		for(int i=0;i<n;i++)
		{
			cin >> a[i];
		}
		
		int ans = 0;
		
		for(int i=1;i<n-1;i++)
		{
			if( a[i-1] > a[i] && a[i] < a[i+1] )
			{
				ans++;
			}
		}
		
		cout << ans << "\n"; 
	}
	
	return 0;
}

:::

## pC 四的倍數 (Multiples of four)

**Prepared by Colten**

$4$ 的倍數的判斷方式為，當最後兩位數為 $4$ 的倍數時，那麼此數則為 $4$ 的倍數。

那麼我們可以利用一個迴圈，並當迴圈發現 $str[i-1] + str[i]$ 轉成整數時，假如可以被 $4$ 整除，那麼代表共有 $i$ 種情況能與 $str[i]$ 做搭配。

舉例 : 假如目前的數字為 $1024$，當發現 $24$ 為 4 的倍數時，其可能的狀況有 $24,024,1024$。

在實作上，多用一個變數去紀錄答案，最後輸出。

:::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);
	
	string a;
	
	cin >> a;
	
	int ans = 0;
	
	int now = 0;
	
	for(int i=0;i<a.size();i++)
	{
		if( i == 0 )
		{
			int u = a[i] - '0';
			
			now = u;
			
			if( u % 4 == 0 )
			{
				ans++;
			}
		}
		else
		{
			int u = a[i] - '0';
			
			now *= 10;
			
			now += u;
			
			if( u % 4 == 0 )
			{
				ans++;
			}
			
			if( now % 4 == 0 )
			{
				ans += i;
			}
			
			now %= 10;
		}
	}
	
	cout << ans << "\n";
	
	return 0;
}

:::

## pD Gunjyo 的點數分配問題 (Gunjyo's Points Allocation Problem)

**Prepared by Colten**

這題其實有對於每組資料 $O(1)$ 的作法 (數學解)，但是對於這種題目更直覺的作法，我們可以對點數進行二分搜，每組時間複雜度 $O(logK)$。

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

#include <bits/stdc++.h>

#define int long long

using namespace std;

void binary_search(int a,int b,int n)
{
	int all = a + n;
	
	int l = 0,r = n;
	
	while( l < r )
	{
		int mid = ( l + r ) / 2;
		
		int u1 = a + mid;
		
		int u2 = b + ( n - mid );
		
		if( u1 > u2 )
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	
	cout << n - l + 1 << "\n";
}
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q;
	
	cin >> q;
	
	while(q--)
	{
		int a,b,c;
		
		cin >> a >> b >> c;
		
		int all = a + c;
		
		if( all <= b )
		{
			cout << 0 << "\n";
		}
		else
		{
			binary_search(a,b,c);
		}
	}
	
	return 0;
} 

:::

## pE 很短的問題 (A Short Problem)

**Prepared by Fysty**

假設所求為 $T$。

考慮集合$S_x=\{x,kx,k^2x,...\}$，其中 $x$ 不被 $k$ 整除。

注意到若 $n=|S_x|$，由鴿籠原理可知 $S_x$ 不可能取超過 $\lceil\frac{n}{2}\rceil$ 個元素，而取恰好$\lceil\frac{n}{2}\rceil$個元素的方法為取 $x,k^2x,k^4x,...$。

再觀察到對於任兩個不被 $k$ 整除的數 $x,y$，不管 $S_x$ 中那些數被選進 $B$，都不會影響 $S_y$ 中哪些被選，所以可推得 $$T=\sum_{k\not\mid x} \big\lceil\frac{|S_x|}{2}\big\rceil$$

但是這不好算，所以觀察所取的所有元素，可以發現恰好取所有最多能被 $k$ 整除偶數次的正整數，所以由排容原理可知 $T=k^n-k^{n-1}+k^{n-2}-...+(-1)^n$。

最後注意到 $kT+T=k^{n+1}+(-1)^n$，因此 $T=\frac{k^{n+1}+(-1)^n}{k+1}$，而這可以用快速冪和費馬小定理在 $O(\log n)$ 計算出來。

總時間複雜度 $O(t\log 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 F first
#define S second
const int MOD=1e9+7;
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);
}
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        cout<<(fpow(k,n+1,MOD)+(n%2?-1:1)+MOD)%MOD*fpow(k+1,MOD-2,MOD)%MOD<<"\n";
    }
}

:::

## pF 彈簧床 (Trampoline)

**Prepared by LittleCube**

### Subtask 1, 2
顯然，暴力:D
沒有任何實作細節
### Subtask 3
看一下題目，其實就是不帶修改的查詢，
如果把每個$k$都維護一次前綴和，就能$O(1)$查詢了，
但是顯然這樣做會MLE，所以可以透過只維護一部份（通常是取$\sqrt N$），
就可以在夠好的記憶體以及夠好的時間完成了。
複雜度：$O(N\sqrt N + Q\sqrt N)$

### Subtask 4, 5
接續剛剛的想法，要帶修改怎麼辦？
所以可以用兩個方式：線段樹或分塊
#### 分塊做法
可以發現每個查詢的位置$\%k$都會是一樣的餘數，
所以修改也只要對那部分的餘數做就好了，
複雜度$O(N\sqrt N + Q\sqrt N)$，不變，只是常數變大。
#### 線段樹做法
假設我維護$M$個數，這樣修改就是$M\log N$，
查詢如果$k>M$就是$\displaystyle \frac{N}{M}$，否則是$\log N$，
所以複雜度是$O(M N\log N + Q \max(\displaystyle \frac{N}{M}, \log N))$
差不多取$M =$ 一個蠻小的數字 就會過。

:::spoiler 參考解答 (C++，分塊)

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int n, q, arr[200005], t, l, r, k, v, sqrtn, block[500][500][500], bi[200005];

int nxt(int i, int k)
{
    int ti = bi[i];
    i += (sqrtn - sqrtn % k);
    if(i <= ti * sqrtn)
        return i + k;
    return i;
}

signed main()
{
    fast;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    sqrtn = sqrt(n);
    for (int i = 1, j = 1; i <= n; j++)
        for (; i <= min(j * sqrtn, n); i++)
        {
            bi[i] = j;
            for (int k = 1; k < sqrtn; k++)
                block[j][k][i % k] += arr[i];
        }

    for (int i = 1; i <= q; i++)
    {
        cin >> t;
        if (t == 1)
        {
            int ans = 0;
            cin >> l >> r >> k;
            int i = l;
            if (bi[l] == bi[r] || k >= sqrtn)
                for (int i = l; i <= r; i += k)
                    ans += arr[i];
            
            else
            {
                for (; i <= min(r, bi[l] * sqrtn); i += k)
                    ans += arr[i];
                for (; i <= (bi[r] - 1) * sqrtn; i = nxt(i, k))
                    ans += block[bi[i]][k][i % k];
                for (; i <= r; i += k)
                    ans += arr[i];
            }

            cout << ans << '\n';
        }
        else
        {
            cin >> l >> v;
            for (int k = 1; k < sqrtn; k++)
                block[bi[l]][k][l % k] += (v - arr[l]);
            arr[l] = v;
        }
    }
}

:::