VOGAME – spoj

Đề bài:

Thuật toán:

  • Mình tham khảo từ solution của anh Lê Anh Đức
    Thuật toán:
    -Nhận xét là tính chẵn lẻ của số bi đỏ ko đổi, vậy nên kết quả sẽ là số bi đỏ modulo 2.
    -Hãy thử tạo 1 test và sinh ra dãy A, các bạn sẽ nhận thấy dãy A tuần hoàn theo chu kì D+1, từ đó có thể giải quyết bài toán này. Sau đây là code của mình:

Code:

#include<bits/stdc++.h>
#define N 100001
using namespace std;
int t,n,d;
long long a[N], s[3];
int main()
{
	cin>>t;
	for (int z=1; z <= t; z++)
		{
			s[0]=s[1]=0;
			cin>>n>>d;
			for (int i=1; i <= d; i++)
				{
					cin>>a[i];
					s[a[i]]=s[a[i]]+1;
				}	
			if (n == d)
				{
					cout<<s[1]%2<<endl;
					continue;
				}
			d=d+1;
			a[d]=s[1]%2;
			s[a[d]]=s[a[d]]+1;
			int ck=n/d;
			int du=n-ck*d;
			long long kq=s[1]*ck;
			for (int i=1; i <= du; i++)
				kq=kq + a[i]%2;
			cout<<kq%2<<endl;
		}
}

PVOI14_6 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
int factorial(int n, long long MOD) {
    int ret = 1;
    for(int i = 1; i <= n; i++) ret = ((long long)(ret) * i) % MOD;
    return ret;
}
 
int power(int x, int k, long long MOD) {
    if (k == 0) return 1;
    long long t = power(x, k / 2, MOD);
    t = (t * t) % MOD;
    if (k % 2 == 1) t = (t * x) % MOD;
    return t;
}
 
int count_in_grid(int m, int n, int s) {
    return max(0, min(max(0, s - 1), m) - max(max(0, s - n), 1) + 1);
}
 
int calc(int m, int n, long long MOD) {
    int x = 1;
    for(int i = 1; i < m + m; i++) {
        int j = m + m + 1 - i;
        int k = count_in_grid(m - n, m - n, j) + 2 * count_in_grid(n, m - n, j - m);
        x = ((long long)(x) * power(i, k, MOD)) % MOD;
    }
    int ret = ((long long)(factorial((long long)(m) * m - (long long)(n) * n, MOD)) * power(x, MOD - 2, MOD)) % MOD;
    return ret;
}
 
int main()
{
    //freopen("L.inp","r",stdin);
    //freopen("L.out","w",stdout);
	int m, n ;
	long long MOD;
    cin >> m >> n >> MOD;
    cout << calc(m, n, MOD);
}

PVOI14_5 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code: (ideone)

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
 
const int MAXN = 1000000 + 10;
const int MAXV = 10000 + 10;
 
int freq[MAXV];
int a[MAXN];
int c[MAXN];
vector<pair<int, int> > b[MAXV];
int n;
 
void init() {
    vector<bool> p(MAXV, true);
    p[0] = p[1] = false;
    for(int i = 2; i * i <= 10000; i++) {
        if (p[i]) {
            int j = i + i;
            while (j <= 10000) {
                p[j] = false;
                j += i;
            }
        }
    }
    vector<int> prime;
    for(int i = 1; i <= 10000; i++) {
        if (p[i]) prime.push_back(i);
    }
    for(int i = 1; i <= 10000; i++) {
        if (freq[i] == 0) continue;
        for(int j = 0; j < prime.size(); j++) {
            int cnt = 0;
            int v = i;
            while (v % prime[j] == 0) {
                cnt++; v /= prime[j];
            }
            b[prime[j]].push_back(make_pair(cnt, freq[i]));
        }
    }
}
 
long long power(int x, int k) {
    long long ret = 1;
    for(int i = 1; i <= k; i++) ret *= x;
    return ret;
}
 
int main()
{
    //freopen("P.inp", "r", stdin);
    //freopen("P.out", "w", stdout);
 
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) freq[a[i]]++;
    init();
    long long ans1 = 0; long long ans2 = 1;
    for(int i = 1; i <= 10000; i++) {
        if (b[i].size() > 0) {
            for(int j = 0; j <= 50; j++) c[j] = 0;
            for(int j = 0; j < b[i].size(); j++) c[b[i][j].first] += b[i][j].second;
            long long tot = 0;
            for(int j = 0; j <= 50; j++) tot += (long long)(j) * c[j];
            int p = (n + 1) / 2, l = 0;
            long long s = 0;
            for(int j = 0; j <= 50; j++) {
                s += (long long)(j) * c[j]; l += c[j];
                if (l >= p) {
                    int kk = (long long)(l) * j - s + (tot - s) - (long long)(n - l) * j;
                    ans1 += (long long)(l) * j - s + (tot - s) - (long long)(n - l) * j;
                    ans2 *= power(i, j);
                    break;
                }
            }
        }
    }
    cout << ans1 << " " << ans2 << endl;
}