## Biển số xe

Nhận thấy rằng, đáp án sẽ chỉ có thể nằm trong tập ước của hiệu hai số bất kì.

Ta có thể lấy một hiệu bất kì ra, tìm ước và thử từng đáp án.

<details>
<summary> Code</summary>

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105];
int ok( int M ) {
	if (M == 1) return 0;
   int ans = a[1]%M;
   for( int i = 2; i <= n; i++)
      if( a[i]%M != ans )
         return 0;
   return 1;
}

int main( ) {
   cin >> n;
   for (int i=1; i<=n; i++) {
   		cin >> a[i];
   }
   int cur = abs (a[1] - a[2]);
   vector<int> res;
	for (int i=1; i*i <= cur; i++) {
		if (cur % i) continue;
		if (ok(i)) res.push_back(i);
		if (cur/i != i) if (ok(cur/i)) res.push_back(cur/i); 
	}
	sort (res.begin(),res.end());
	for (auto u : res) cout << u << ' ';
   return 0;
}

</details>

## Seqk

Ta cần tìm đoạn $[L,R]$ dài nhất sao cho $pre[R] - pre[L-1] = k$.

Do mảng $pre$ tăng dần nên có thể sử dụng tìm kiếm nhị phân, hoặc dùng ``map<int,int>``.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+6;
int f[N],s[N];
int pos[N];
int n,k;
int a[N];
map<int,int> m;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    int ans=0;
    for (int i=1; i<=n; i++){
        cin>>a[i]; s[i]=s[i-1]+a[i];
        if (s[i]==k) ans=i;
        else {
            if (m[s[i]-k]) {
                ans=max(ans,i-m[s[i]-k]);
            }
        }
        if (m[s[i]]==0) m[s[i]]=i;
    }
    cout<<ans;
}

</details>

## Dọn tuyết

Gọi $f(i,j)$ là số cách để xét tới thùng thứ $i$ và đã trọn ra được $j$ con búp bê.

Ta có hai trường hợp khi xét tới trạng thái $(i,j)$:
- Không chọn búp bê trong hộp $i$, ta sẽ cộng thêm lượng $f(i-1,j)$.
- Chọn búp bê trong hộp $i$, ta sẽ cộng thêm lượng $f(i-1,j-1)*a[i]$

<details>
<summary> Code </summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1005;
int n,m;
int f[N][N];
int a[N];
const int mod = 1e9+7;
signed main() {
	cin >> n >> m;
	f[0][0] = 1;
	for (int i=1; i<=n; i++) cin >> a[i], f[i][0] = 1;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			f[i][j] = f[i-1][j] + (f[i-1][j-1]*a[i])%mod;
			f[i][j] %= mod;
		}
	}
	cout << f[n][m];
}

</details>

## 3 số nguyên tố

Ta chỉ cần sàng để tìm các số nguyên tố trong khoảng $[1,10^6+100]$m sau đó thử từng bộ ba số nguyên tố liên tiếp một để kiểm tra.

<details>
<summary>Code </summary>

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxp = 1e6 + 100;
    int prime[maxp];
    vector<int> p;
    void sieve(){
        for(int i = 1; i < maxp; i++) prime[i] = i;
        for(long long i = 2; i < maxp; i++){
            if(prime[i] == i){
                p.push_back(i);
                for(long long j = i * i; j < maxp; j += i){
                    prime[j] = i;
                }
            }
        }
    }
    

    void solve(){
        sieve();

        int n;
        cin >> n;
        for(int i = p.size() - 3; i >= 0; i--){
            if(p[i] * p[i + 1] * p[i + 2] <= n){
                cout << p[i] * p[i + 1] * p[i + 2] << endl;
                return;
            }
        }

        cout << -1;
        cout << endl;
    }
    
    signed main(){
        solve();
    }

</details>

## Trung bình cộng

Cần tìm dãy $[L,R]$ sao cho:
- $\frac{a_L+a_{L+1}+...+a_R}{R-L+1} \ge k$

--> $a_L+a_{L+1}+...+a_R \ge k*(R-L+1)$
--> $(a_L-k) + (a_{L+1}-k) + ... + (a_R - k) \ge 0$

Vậy nếu ta trừ mỗi phần tử $a_i$ cho $k$, bài toán sẽ quy về tìm đoạn con dài nhất có tổng không âm.

<details>
<summary> Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+6;
int f[N],s[N];
int pos[N];
int n,k;
int a[N];
int bs (int l, int r, int x){
    int ans=-1;
    while (r>=l) {
        int mid=(r-l)/2+l;
        if (f[mid]-x>=0) {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for (int i=1; i<=n; i++){
        cin>>a[i];
        a[i]-=k;
    }
    for (int i=n; i>=1; i--){
        s[i]=s[i+1]+a[i];
    }
    int j=1;
    int ans=0;
    for (int i=1; i<=n; i++) {
        if (j==1||s[i]>f[j-1]) {
            f[j]=s[i];
            pos[j]=i;
            j++;
        }
        int b= bs(1,j-1, s[i+1]);
        if (b!=-1) {
            ans=max(ans,i-pos[b]+1);
        }
    }
    cout<<ans;
}

</details>

## CKN

Bài này ta cần code đủ $3$ subtaks để AC.

### Subtask 1

Ta có thể tính $C(i,j)$ với $i = n$, $j = k$ qua công thức quy hoạch động như sau:
- Có hai trường hợp, lấy phần tử $i$ hoặc không.
- $C(i,j) = C(i-1,j) + C(i-1,j-1)$

### Subtask 2

Dựa vào công thức: $\frac{n!}{k!\times(n-k)!}$, ta có thể phân tích thừa số nguyên tố của tử và mẫu sau đó trừ cho nhau để ra dạng phân tích thừa số nguyên tố của kết quả.

### Subtask 3

Từ: $\frac{n!}{k!\times(n-k)!}$, đặt $A = n!$, $B = k!$, $C = (n-k)!$.

Ta cần tính $\frac{A}{B\times C} \% mod$

Hay: $A \times B^{-1} \times C^{-1} \% mod$

Theo định lý Fermat nhỏ, ta lại có: $a^{-1} \% p = a^{p-2} \% p$ với $p$ là số nguyên tố và $(a,p) = 1$

Vậy ta cần tính: $A \times B^{mod-2} \times C^{mod-2} \% mod$ (do $mod$ ở subtask này nguyên tố).

<details>
<summary> Code </summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,mod;
namespace sub1 {
	const int N = 2005;
	int f[N][N];
	void cal () {
		int n = 2000, m = 2000;
		f[0][0] = 1;
		for (int i=1; i<=n; i++) {
			f[i][0] = f[i-1][0];
			for (int j=1; j<=i; j++) {
				f[i][j] = f[i-1][j-1] + f[i-1][j];
				f[i][j] %= mod;
			}
		}
	}
	void solve () {
		cin >> t >> mod;
		cal();
		while (t--) {
			int n,k; cin >> n >> k;
			cout << f[n][k] << endl;
		}
	}
}
namespace sub2 {
	const int N = 1e5+5;
	int p[N];
	void sieve() {
		int n = 1e5;
		for (int i=2; i<=n; i++) p[i] = i;
		for (int i=2; i*i <=n; i++) {
			if (p[i] == i)for (int j=i*i; j<=n; j+=i) p[j] = i;
		}
	}
	int cnt[N];
	void solve () {
		sieve();
		cin >> t >> mod;
		int n,k;
		cin >> n >> k;
		for (int i=1; i<=n; i++) cnt[i] = 0;
		for (int i=2; i<=n; i++) {
			int x = i;
			while (x != 1) {
				int y = p[x];
				while (x%y == 0) x/=y, cnt[y]++;
			}
		}
		for (int i=2; i<=k; i++) {
			int x = i;
			while (x != 1) {
				int y = p[x];
				while (x%y == 0) x/=y, cnt[y]--;
			}
		}
		for (int i=2; i<=n-k; i++) {
			int x = i;
			while (x != 1) {
				int y = p[x];
				while (x%y == 0) x/=y, cnt[y]--;
			}
		}
		int res = 1;
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=cnt[i]; j++) res = res*i%mod;
		}
		cout << res << endl;
	}
}
namespace sub3 {
	const int N = 1e5+5;
	int gt[N],inv[N];
	int cdt(int a, int b) {
		if (b == 0) return 1;
		int t = cdt(a,b/2);
		if (b%2) return t*t%mod*a%mod;
		else return t*t%mod;
	} 
	void cal () {
		int n = 1e5;
		gt[0] = 1;
		inv[0] = 1;
		for (int i=1; i<=n; i++) gt[i] = gt[i-1]*i%mod, inv[i] = cdt(gt[i],mod-2);
	}
	int ckn (int k, int n) {
		return gt[n]*inv[k]%mod*inv[n-k]%mod;
	}
	void solve () {
		cin >> t >> mod;
		cal();
		while (t--) {
	    	int n,k; cin >> n >> k;
			cout << ckn (k,n) << '\n';
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int sub; cin >> sub;
	if (sub == 1) sub1::solve();
	else if (sub == 2) sub2::solve();
	else sub3::solve();
}

</details>