UVA 11255 - Necklace

第一次練Burnside@@
主要是把每次fix point的個數算出來就好惹。
雖然複雜度可以壓到O(40^3 + N*(a+b+c))但反正會過XD

1. 算
2. 把答案存起來XD

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long int int64;

struct Key{int a, b, c; Key(int _a, int _b, int _c):a(_a), b(_b), c(_c){return;}};
bool operator==(const Key& p, const Key& q){return p.a == q.a and p.b == q.b and p.c == q.c;}
struct KeyHash{size_t operator()(const Key& key)const{ return (hash<int>()(key.a)<<14)^(hash<int>()(key.b)<<7)^hash<int>()(key.c);}};

void dumpvec(vector<int>& vec){printf("vec:");for(int ii : vec) printf(" %d", ii);printf("\n");return;}

struct Ans{int v[3]; Ans(int a, int b, int c){v[0] = a, v[1] = b, v[2] = c; sort(v, v+3);return;}};
bool operator==(const Ans& p, const Ans& q){return p.v[0] == q.v[0] and p.v[1] == q.v[1] and p.v[2] == q.v[2];}
struct AnsHash{size_t operator()(const Ans& a)const{return (hash<int>()(a.v[0])<<14)^(hash<int>()(a.v[1])^7)^hash<int>()(a.v[2]);}};

int main(){
    int N; scanf("%d", &N);
    unordered_map<Ans, int64, AnsHash> anstab;
    while(N--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        if(anstab.count(Ans(a, b, c))){
            printf("%lld\n", anstab[Ans(a, b, c)]);
            continue;
        }

        int64 ans = 0;
        int n = a+b+c;
       
        // 0-turn
        for(int tptr = 0;tptr < n;tptr++){
            bool vis[40] = {0};
            vector<int> vec;
            for(int lx = 0;lx < n;lx++){
                int cc = 0;
                int ptr = lx;
                while(!vis[ptr]){
                    vis[ptr] = 1;
                    cc++;
                    ptr = (ptr+tptr)%n;
                }
                if(cc) vec.push_back(cc);
            }
            unordered_map<Key, int64, KeyHash> bfs[2];
            bfs[0][Key(a, b, c)] = 1;
            int pp = 0;
            for(int dt : vec){
                bfs[pp^1].clear();
                for(auto it : bfs[pp]){
                    Key k = it.first; int64 val = it.second;
                    if(k.a >= dt) bfs[pp^1][Key(k.a-dt, k.b, k.c)] += val;
                    if(k.b >= dt) bfs[pp^1][Key(k.a, k.b-dt, k.c)] += val;
                    if(k.c >= dt) bfs[pp^1][Key(k.a, k.b, k.c-dt)] += val;
                }
                pp ^= 1;
            }
            ans += (int64)bfs[pp][Key(0, 0, 0)];
        }
       
        // 1-turn
        for(int tptr = 0;tptr < n;tptr++){
            bool vis[40] = {0};
            vector<int> vec;
            for(int lx = 0;lx < n;lx++){
                int cc = 0;
                int ptr = lx;
                while(!vis[ptr]){
                    vis[ptr] = 1;
                    ptr = (n-1-ptr+tptr)%n;
                    cc++;
                }
                if(cc) vec.push_back(cc);
            }
            unordered_map<Key, int64, KeyHash> bfs[2];
            bfs[0][Key(a, b, c)] = 1;
            int pp = 0;
            for(int dt : vec){
                bfs[pp^1].clear();
                for(auto it : bfs[pp]){
                    Key k = it.first; int64 val = it.second;
                    if(k.a >= dt) bfs[pp^1][Key(k.a-dt, k.b, k.c)] += val;
                    if(k.b >= dt) bfs[pp^1][Key(k.a, k.b-dt, k.c)] += val;
                    if(k.c >= dt) bfs[pp^1][Key(k.a, k.b, k.c-dt)] += val;
                }
                pp ^= 1;
            }
            ans += (int64)bfs[pp][Key(0, 0, 0)];
        }
       
        anstab[Ans(a, b, c)] = ans/2/n;

        printf("%lld\n", ans/2/n);
    }
    return 0;
}