fq.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
char iq[2000];
int ql;
int mem[1500][1500];
int count(int left5, int left10)
{
int result, pos;
if (left5 < 0 || left10 < 0) return 0;
if (left5 == 0 && left10 == 0) return 1;
if (left10 < left5) return 0;
if (mem[left5][left10] >= 0) return mem[left5][left10];
pos = ql - left5 - left10;
if (iq[pos] == '(') {
result = count(left5-1, left10);
} else if (iq[pos] == ')') {
result = count(left5, left10-1);
} else {
result = (count(left5-1, left10) + count(left5, left10-1)) % 1000000;
}
//printf("pos %d l5 %d l10 %d ch %c ret %d\n", pos, left5, left10, iq[pos], result);
mem[left5][left10] = result;
return result;
}
int main(int argc, char **argv)
{
int rv;
while (1) {
printf("%d\n", count
(ql
/2, ql
/2)); }
return 0;
}