LuoguP5440 - 【XR-2】奇迹

// 调用方法: dfs(8, 0, 0, 0)
int dfs(int nown, int num, int rn, int jy) {
	if(nown == 0) {
    // 日期全部枚举完
		if(num / 10000 == 0) return 0;
    // 非常关键，0不能当年份（我一开始没加就得10分）
		if(rn && pdrn(num / 10000) == 0) return 0;
    // 如果必须为闰年就判断年份
		return pdzs(num);
    // 总日期还得为质数
	}
	if(nown == 6) {
    // 枚举完日
		if(num == 0 || num > 31 || !pdzs(num)) return 0;
    // 如果是等于0日、31日以上或不是质数就return
		if(num == 31) jy= 1;
    // 如果是31日就必须为大月
	}
	if(nown == 4) {
    // 判断完日、月
		if(num < 32 || num > 1231 || !pdzs(num)) return 0;
    // 如果是等于0月、13月以上或不是质数就return
		if(jy && !yue[num / 100]) return 0;
    // 如果必须为大月就判断月份num / 100，yue数组代表是否为大月
		if(num / 100 == 2) {
			if(num % 100 > 29) return 0;
        // 2月最多29天
			if(num % 100 == 29) rn= 1;
        // 如果是2月29日就必须为闰年
		}
	}
	if(a[nown] != -1) return dfs(nown - 1, a[nown] * p10[8 - nown] + num, rn, jy);
    // 如果输入给出就直接进入下一层，p10数组相当于pow10
	int res= 0;
	for(int i= 0; i <= 9; i++) res+= dfs(nown - 1, i * p10[8 - nown] + num, rn, jy);
    // 枚举0~9为此位
	return res;
}

// 筛10005以内的质数
inline void init() {
	flag[1]= 1;
	for(int i= 2; i < 10005; i++) {
		if(!flag[i]) prim[++tot]= i;
		for(int j= 1; j <= tot; j++) {
			if(i * prim[j] >= 10005) break;
			flag[i * prim[j]]= 1;
			if(i % prim[j] == 0) break;
		}
	}
	return;
}
// 判断质数
inline int pdzs(int x) {
	if(x < 2) return 0;
	for(int i= 1; i <= tot; i++)
		if(x % prim[i] == 0) return x == prim[i];
	return 1;
}

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int n, a[9], prim[10005], flag[10005], tot;
char tmpc;
int p10[]= {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
int yue[]= {0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1};
inline void init() {
	flag[1]= 1;
	for(int i= 2; i < 10005; i++) {
		if(!flag[i]) prim[++tot]= i;
		for(int j= 1; j <= tot; j++) {
			if(i * prim[j] >= 10005) break;
			flag[i * prim[j]]= 1;
			if(i % prim[j] == 0) break;
		}
	}
	return;
}
inline int pdrn(int x) {
	return (x % 4 == 0 && x % 100 != 0) || (x % 400 == 0 && x % 3200 != 0);
}
inline int pdzs(int x) {
	if(x < 2) return 0;
	for(int i= 1; i <= tot; i++)
		if(x % prim[i] == 0) return x == prim[i];
	return 1;
}
int dfs(int nown, int num, int rn, int jy) {
	if(nown == 0) {
		if(num / 10000 == 0) return 0;
		if(rn && pdrn(num / 10000) == 0) return 0;
		return pdzs(num);
	}
	if(nown == 6) {
		if(num == 0 || num > 31 || !pdzs(num)) return 0;
		if(num == 31) jy= 1;
	}
	if(nown == 4) {
		if(num < 32 || num > 1231 || !pdzs(num)) return 0;
		if(jy && !yue[num / 100]) return 0;
		if(num / 100 == 2) {
			if(num % 100 > 29) return 0;
			if(num % 100 == 29) rn= 1;
		}
	}
	if(a[nown] != -1) return dfs(nown - 1, a[nown] * p10[8 - nown] + num, rn, jy);
	int res= 0;
	for(int i= 0; i <= 9; i++) res+= dfs(nown - 1, i * p10[8 - nown] + num, rn, jy);
	return res;
}
char get() {
	char ch= getchar();
	while((ch < '0' || ch > '9') && ch != '-') ch= getchar();
	return ch;
}
void put(int x) {
	if(x > 9) put(x / 10);
	putchar('0' + x % 10);
	return;
}
int main() {
	init(), cin >> n;
	while(n--) {
		for(int i= 1; i <= 8; i++) tmpc= get(), a[i]= (tmpc == '-' ? -1 : tmpc - '0');
		put(dfs(8, 0, 0, 0)), putchar('\n');
	}
	return 0;
}