circle.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <set>

using namespace std;

#define long long long

int n, k;

char a[11][12309];

long _2309_n=1;

set<long> T;

bool minimize(long &a, long b){ if (a>b) a=b; else return false; return true; }

long hash(char a[]){

    static long H[12309];

    int i;

    H[0]=0;

    for (i=1; i<=n; i++) a[i+n]=a[i];

    for (i=1; i<=n*2; i++) H[i]=H[i-1]*2309+a[i];

    long answer=H[n];

    for (i=1; i<=n; i++) minimize(answer, H[i+n]-H[i]*_2309_n);

    return answer;

}

void show(char a[]){

    for (int i=1; i<=n; i++)

    printf(a[i] ? "W" : "B");

    printf("\n");

    printf("%lld\n", hash(a));

}

void back(int k){

    int i;

    if (k==0) { /*show(a[k]);*/ T.insert(hash(a[k])); return; }

    a[k-1][0]=0;

    for (i=1; i<=n; i++)

    a[k-1][i] = a[k-1][i-1] ^ a[k][i];

    if (a[k-1][n]==a[k-1][0])

    back(k-1);

    a[k-1][0]=1;

    for (i=1; i<=n; i++)

    a[k-1][i] = a[k-1][i-1] ^ a[k][i];

    if (a[k-1][n]==a[k-1][0])

    back(k-1);

}

main(){

    int i, j;

    scanf("%d%d", &n, &k);

    scanf("%s", a[0]+1);

    for (i=1; i<=n; i++) a[0][i] &= 1;

    for (j=1; j<=k; j++) {

        a[j-1][0]=a[j-1][n];

        for (i=1; i<=n; i++) a[j][i] = a[j-1][i-1] ^ a[j-1][i];

    }

    for (i=1; i<=n; i++) _2309_n *= 2309;

    back(k);

    printf("%d\n", T.size());

}

Nhận xét