主要是把每次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;
}
