DEGREE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int dp[35][35],base[35],bin[35];
void init()
{
    dp[0][0]=base[0]=1;
    for(int i=1;i<=32;i++)
    {
        dp[i][0]=1;
        base[i]=base[i-1]<<1;
        for(int j=1;j<=i;j++)
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
    }
}
int calc(int x,int k)
{
    int i,one=0,ans=0;
    for(i=31;i>=0;i--)
    {
        if(x&base[i])
        {
            if(one>k)
                break;
            ans+=dp[i][k-one];
            one++;
            x-=base[i];
        }
    }
    if(one==k)
        ans++;
    return ans;
}
int getbin(int x,int b)
{
    int ct=0,i,ret=0;
    if(!x)
        return x;
    while(x)
    {
        bin[ct++]=x%b;
        x/=b;
    }
    for(i=ct-1;i>=0;i--)
    {
        if(bin[i]>1)
            break;
        if(bin[i])
            ret=ret<<1|1;
        else
            ret<<=1;
    }
    while(i>=0)
    {
        ret=ret<<1|1;
        i--;
    }
    return ret;
}
int main()
{
    int x,y,k,b;
 
    init();
    while(~scanf("%d%d%d%d",&x,&y,&k,&b))
    {
        y=getbin(y,b);
        x=getbin(x-1,b);
        printf("%d\n",calc(y,k)-calc(x,k));
    }
    return 0;
}

listgame – kattis

Đề bài
Thuật toán
Code

SHHV – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 13;
const int oo = 1e9+3;
string s;
 
ll gt[MAXN+1];
int n, x, a[MAXN+1], b[MAXN+1], i, j;
bool chon[MAXN+1];
ll t;
 
void init() {
    gt[0] = 1;
    gt[1] = 1;
    for (int i=2; i<=MAXN; i++) gt[i] = gt[i-1]*i;
}
 
void query1() {
    ll ans = 0;
    memset(chon,0,sizeof(chon));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]-1; j++)
        if (!chon[j]) {
            ans += gt[n-i];
        }
        chon[a[i]] = 1;
    }
    cout << ans+1 << endl;
}
 
void query2() {
    memset(chon,0,sizeof(chon));
    t--;
    for (i=1; i<=n; i++) {
        int tmp = 0;
        for (j=1; j<=n; j++) {
            if (!chon[j]) tmp++;
            if (gt[n-i]*tmp>t) break;
        }
        t -= gt[n-i]*(tmp-1);
        b[i] = j;
        chon[j]=1;
    }
    for (int i=1; i<=n; i++) cout << b[i] << " ";
}
 
int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    while (cin>>a[++n]);
    t=a[--n]; n--;
    init();
    query1();
    query2();
    return 0;
}

FIBVAL – spoj

Đề bài

Thuật toán

Để giải được bài này, ta cần áp dụng 1 tính chất đặc biệt của dãy Fibonacci, đó là chu kỳ Pisano

Dãy Fibonacci có dạng:

  • f(0) = 0
  • f(1)=1
  • f(i)=f(i-1)+f(i-2)

Đối với 1 số nguyên n bất kì thì dãy g(i)=f(i) mod n có tính chu kì.

Ví dụ: Với n=3 ta có:

f 0 1 1 2 3 5 8 13 15 28 43
g 0 1 1 2 0 2 2 1 0 1 1

Ở bài này, ta có chu kì gồm 7 nốt nhạc vì vậy ta xét tính chu kì trên dãy g(i)=f(i) mod 7.

Chu kì Peisano của 7 trong bài này gồm 16 số:

 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1

Như vậy, độ dài đoạn nhạc dài nhất có tính chu kì chỉ có thể là 2 hoặc có dạng 16*k.

Code

CONST
    tfi = '';
    tfo = '';
VAR
    fi,fo           : text;
 
Function pro(l,r: longint): longint;
    Var
        len,res: longint;
    Begin
        len:=r-l+1;
        l:=l mod 16;
        r:=r mod 16;
        If l=0 then l:=16;
        If r=0 then r:=16;
        res:=len div 16;
        If len>=32 then exit(res*16)
        else
            If len>=9 then exit(2)
            else
                If ((l=9)) or ((l>9) and (r0 do
            begin
                read(fi,l,r);
                writeln(fo,pro(l,r));
                dec(test);
            end;
    End;
 
BEGIN
    assign(fi,tfi); reset(fi);
    assign(fo,tfo); rewrite(fo);
        process;
    close(fi); close(fo);
END.

Nguồn: không rõ

C11SUM – spoj

Đề bài:

Thuật toán:

  • Các bạn đọc code xem thuật toán dễ thế nào nhé 🙂

Code:

{$H+}
Uses math;
Const
	inp = '';
	out = '';
	maxn = 1000001;
	oo = 1000000007;
 
Var
	a,b : array [0..maxn] of int64;	
	s : string;
	n,i,x : longint;
	res,hold : int64;
 
begin
	assign(input,inp); reset(input);
	assign(output,out); rewrite(output);
	readln(s);
	n := length(s);
	hold := 0;
	for i := 1 to n do
	  begin
	  	x := ord(s[i])-ord('0');
	  	hold := (hold*10+i*x) mod oo;
	  	res := (res +hold) mod oo;
	  end;
	writeln(res);
end.

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);
}