這題真的要讓我大爆炸啦！
由於本人不怎麼精明，剪枝不太會減，所以一直TLE
題目：
製造出5X5方陣，每行(由上而下)，每列(左而右)，兩條對角線(左而右)，皆是五位數(10000<=n<=99999)質數。
而且每一位數(digit)的和(sum)都是一個指定的數字a，且左上角(0, 0)的數字也是指定的數字b
如果有多組解，由r0 c0，r0c1，...的大小依序排列，每組解空一行輸出，最後無空行。

有兩個出發點：
1.產生所有可能的方陣，檢驗是否符合條件。
2.產生所有可能的質數，放上去，檢驗條件。
顯然，五位數的質數密度"dπ(x) /dx"是很低的，第二種方法效率高多了。

於是，先產生質數表，然後帶進去。
問題是，順序呢？要怎麼帶才能早一點進行檢驗、早一點剪枝？
很明顯的，要是用r0, r1, r2, r3, r4絕對會爆掉，我用的方法是c0, r0, c1, r1...
雖然要做10次，但是數字的自由度仍然是14(25維 - 左上角指定數字-行、列、對角線的限制)
做10次、代表早一點剪枝。
問題是，仍然會TLE，最大的測資(數字和23)會跑5秒以上。
於是，要讓每一層的迭代複雜度愈小愈好。
我於是做了一個位數->整數的映射表例如NUM(a1, a2, a3, a4, a5)可以得到一個五位數
以及整數->位數的應射表，一堆恐怖的預處理。
還是不太夠，時間會到3 ~ 5秒，但限制是2秒

於是，我做了一件常人不會做，非?？植赖氖虑?-------用template展開迴圈和遞迴
由於5x5這個大小是固定的，是個編譯期常數，我們就可以把任何for(int i = 0; i <5; ++i)這樣的迴圈展開
還有，任何關於這裡是第幾行、第幾列的 if 檢驗式也可以用template特化來做。
以下是噁心的程式碼，他在最後一筆(和為23)以1.642秒驚險過關了(USACO的電腦還蠻快的)。
希望各位看得懂template 在做什麼、是怎麼運作的。
有興趣可以抓下來編譯，輸入檔(prime3.in)的格式是：
(數字和) (左上角數字)
/*
PROG: prime3
LANG: C++
*/
#include<cstdio>
#include<algorithm>
#define NUM(A,B,C,D,E) (number[A][B][C][D][E])
using namespace std;
static const int MAX_P = 100000;
static const int MAX_S = 10000;
static const int size = 5;
bool notprime[MAX_P];
bool islegalprime[MAX_P];
bool islegalprimenotzero[MAX_P];
int primes[MAX_P / 10];
int primeshead[MAX_P / 10];
int number[10][10][10][10][10];
int parse[MAX_P][size];
int div10[MAX_P];

int *pstart[5][MAX_P];
int *phstart[11];
int *pp = primes;
int *pph = primeshead;
int solutions[MAX_S][size][size];
int ssize;
char matrix[size][size];
int h, sum;
int counter[size * 2];
int sols[MAX_S];
int colnum[size];
int colsum[size];
int rownum[size];
int rowsum[size];

static const int pow10i[] = {10000, 1000, 100, 10, 1};
/*參數分別是：第幾層遞迴、第幾行/列、遞迴上界*/
template<int N = 0, int IND = 0, int UPPER = size>
struct operate
{
    static inline void OP1()
    {
        copy(matrix[N], matrix[N] + size, solutions[ssize][N]);
/*進行下一層遞迴*/
        operate<N + 1, IND, UPPER>::OP1();
    }
    static inline void OP2()
    {
            colnum[N] *= 10;
            colnum[N] += matrix[IND][N];
            operate<N + 1, IND, UPPER>::OP2();
    }
    static inline void OP3()
    {
            colnum[N] = div10[colnum[N]];
            operate<N + 1, IND, UPPER>::OP3();
    }
    static inline void OP4(int i)
    {
            matrix[IND][size - N - 1] = parse[i][N];
            operate<N + 1, IND, UPPER>::OP4(i);
    }
    static inline void OP5(int i)
    {
            matrix[size - N - 1][IND] = parse[i][N];
            operate<N + 1, IND, UPPER>::OP5(i);
    }
    static inline void OP6()
    {
            rownum[N] *= 10;
            rownum[N] += matrix[N][IND];
            operate<N + 1, IND, UPPER>::OP6();
    }
    static inline void OP7()
    {
            rownum[N] = div10[rownum[N]];
            operate<N + 1, IND, UPPER>::OP7();
    }
};
template<int IND, int UPPER>
/*遞迴達到上界(UPPER)，不做任何事*/
struct operate<UPPER, IND, UPPER>
{
    static inline void OP1()
    {
    }
    static inline void OP2()
    {
    }
    static inline void OP3()
    {
    }
    static inline void OP4(int)
    {
    }
    static inline void OP5(int)
    {
    }
    static inline void OP6()
    {
    }
    static inline void OP7()
    {
    }
};
/*對解答排序的比較函數*/
bool cmp(const int a, const int b)
{
    for(int i = 0; i < size; ++i)
        for(int j = 0; j < size; ++j)
        {
            if(solutions[a][i][j] < solutions[b][i][j]) return true;
            else if(solutions[b][i][j] < solutions[a][i][j]) return false;
        }
    return false;
}
/*是否為符合條件的質數*/
inline bool legalprime(int n, bool allow0 = true)
{
    if(n < MAX_P / 10 || notprime[n]) return false;
    int s = 0;
    while(n > 0)
    {
        if(!allow0 && n % 10 == 0) return false;
        s += n % 10;
        n /= 10;
    }
    return s == sum;
}
/*Binary search找出前pos位數字為head的質數的下界*/
inline int* select(int pos, int head, int *prime, int *end)
{
    int s = 0, e = end - prime;
    int ans = e;
    while(s <= e)
    {
        int mid = s + e >> 1;
        if(prime[mid] / pow10i[pos] < head)
        {
            s = mid + 1;
        }
        else
        {
            ans = mid;
            e = mid - 1;
        }
    }
    return prime + ans;
}
/*找到解，複製解答到solutions裡*/
inline void setAns()
{
    operate<>::OP1();
    sols[ssize] = ssize;
    ++ssize;
}
/*以下是爆搜*/
template<int ind> 
inline void processCol();
template<int ind> 
inline void processRow()
{
    int j;
    ++counter[ind * 2 + 1];
    static const int pos = ind;
    int head = rownum[ind];
    int *i = pstart[pos][head];
    int *end = pstart[pos][head + 1];
    for(; i != end; ++i)
    {
        int cur = *i;
        static const int high = size - pos - 1;
        operate<0, ind, high>::OP4(*i);
        bool toprune = false;
        operate<0, ind>::OP2();
        if(!toprune) processCol<ind + 1>();
        operate<0, ind>::OP3();
    }
}
template<>
inline void processRow<4>()
{
        int s = NUM(matrix[0][0], matrix[1][1], matrix[2][2], matrix[3][3], matrix[4][4]);
        if(!islegalprime[s]) return;
        s = NUM(matrix[size - 1][0], matrix[size - 1][1], matrix[size - 1][2], matrix[size - 1][3], matrix[size - 1][4]);
        if(!islegalprime[s]) return;
        setAns();
}
template<int ind>
inline void processCol()
{
    ++counter[ind * 2];
    static const int pos = ind - 1;
    int head = colnum[ind];
    int *i = pstart[pos][head];
    int *end = pstart[pos][head + 1];
    for(; i != end; ++i)
    {
        static const int high = size - pos - 1;
        operate<0, ind, high>::OP5(*i);
        bool toprune = false;
        operate<0, ind>::OP6(); 
        if(!toprune) processRow<ind>();
        operate<0, ind>::OP7();
    }
}
/*第2行的時後檢查左下-右上對角線*/
template<>
inline void processCol<2>()
{
    static const int ind = 2;
    ++counter[4];
    static const int pos = 1;
    int head = colnum[2];
    int *i = pstart[pos][head];
    int *end = pstart[pos][head + 1];
    for(; i != end; ++i)
    {
        static const int high = size - pos - 1;
        for(int j = 0; j < high; ++j)
        matrix[size - j - 1][2] = parse[*i][j];
        int s = NUM(matrix[4][0], matrix[3][1], matrix[2][2], matrix[1][3], matrix[0][4]);
        if(!islegalprime[s]) continue;
        bool toprune = false;
        operate<0, ind>::OP6();
        if(!toprune) processRow<2>();
        operate<0, ind>::OP7();
    }
}
/*第0行、列不允許有0出現的特例*/
inline void row0()
{
    ++counter[1];
    int *start = phstart[h];
    int *end = phstart[h + 1];
    for(int *i = start; i != end; ++i)
    {
        int cur = *i;
        operate<0, 0>::OP4(*i);
        operate<0, 0>::OP2();
        processCol<1>();
        operate<0, 0>::OP3();
    }
}
inline void col0()
{
    ++counter[0];
    int *start = phstart[h];
    int *end = phstart[h + 1];
    for(int *i = start; i != end; ++i)
    {
        int cur = *i;
        operate<0, 0>::OP5(*i);
        operate<0, 0>::OP6();
        row0();
        operate<0, 0>::OP7();
    }
}
/*開始的按鈕*/
void start()
{
    matrix[0][0] = h;
    for(int i = 0; i < size; ++i) 
        rownum[i] = colnum[i] = 0;
    col0();
}
int main()
{
    FILE *fin = fopen("prime3.in", "r"), *fout = fopen("prime3.out", "w");
    fscanf(fin, "%d%d\n", & sum, &h);
    for(int i = 2; i != MAX_P; ++i)
    {
        if(!notprime[i]) 
            for(long long j = (long long) i * i; j < MAX_P; j += i)
                notprime[j] = true;
    }
    for(int i = MAX_P / 10; i != MAX_P; ++i)
    {
        if(legalprime(i)) 
        {
            islegalprime[i] = true;
            *(pp++) = i;
        }
        if(legalprime(i, false)) 
        {
            islegalprimenotzero[i] = true;
            *(pph++) = i;
        }
    }
    /* precompute the lower-bound*/
    for(int i = 1; i <= 10; ++i)
        pstart[0][i] = select(0, i, primes, pp);
    for(int i = 10; i <= 100; ++i)
        pstart[1][i] = select(1, i, primes, pp);
    for(int i = 100; i <= 1000; ++i)
        pstart[2][i] = select(2, i, primes, pp);
    for(int i = 1000; i <= 10000; ++i)
        pstart[3][i] = select(3, i, primes, pp);
    for(int i = 10000; i <= 100000; ++i)
        pstart[4][i] = select(4, i, primes, pp);
    for(int i = 1; i <= 10; ++i)
        phstart[i] = select(0, i, primeshead, pph);
/*整數->位數 以及位數->整數的映射表*/
    for(int i = 0; i < 10; ++i)
        for(int j = 0; j < 10; ++j)
            for(int k = 0; k < 10; ++k)
                for(int l = 0; l < 10; ++l)
                    for(int m = 0; m < 10; ++m)
                    {
                        int cur = i * 10000 + j * 1000 + k * 100 + l * 10 + m;
                        number[i][j][k][l][m] = cur;
                        parse[cur][4] = i;
                        parse[cur][3] = j;
                        parse[cur][2] = k;
                        parse[cur][1] = l;
                        parse[cur][0] = m;
                    }
/*對數字除以10的預處理(除法很慢)*/
    for(int i = 0; i < MAX_P; ++i)
        div10[i] = i / 10;
    start();
/*對解答排序*/
    sort(sols, sols + ssize, cmp);
/*輸出*/
    for(int i = 0; i < ssize; ++i)
    {
        for(int j = 0; j < size; ++j)
        {
            for(int k = 0; k < size; ++k)
            {
                putc('0' + solutions[sols[i]][j][k], fout);
            }
            putc('\n', fout);
        }
        if(i != ssize - 1) putc('\n', fout);
    }
/*若無解*/
    if(ssize = 0) fprintf(fout, "NONE\n");
/*這邊是分析用的計數器*/
    for(int i = 0; i < size * 2; ++i)
        printf("ind:%d times: %d\n", i, counter[i]);
    return 0;
}