結城浩さんのCodeIQの問題「王女様の宝石パターンを見つけよう！」の解答コードです。ローカルで0.3秒くらいで求まります。

gemstring.c

#include <stdio.h>

/* [a][b][c][d][e][f][g][pos][gf] */
long long memoBuffer[5][5][5][5][5][5][5][20][2];

int targetLength;
int targetPuttern[20];

/**
 * 引数に対応するメモの位置を求める
 * @param gemNums 各宝石の残りの数
 * @param pos 現在位置
 * @param gf ギリギリフラグ : 上の桁が指定パターンと一致しているなら1、いないなら0
 */
long long* getMemoPtr(const int gemNums[7],int pos,int gf) {
	return &memoBuffer
		[gemNums[0]][gemNums[1]][gemNums[2]][gemNums[3]][gemNums[4]][gemNums[5]][gemNums[6]]
		[pos][gf];
}

/**
 * 辞書順で指定パターンまでに何パターンあるか求める
 * @param gemNums 各宝石の残りの数
 * @param pos 現在位置
 * @param gf ギリギリフラグ : 上の桁が指定パターンと一致しているなら1、いないなら0
 */
long long tansaku(const int gemNums[7],int pos,int gf) {
	long long* memo=getMemoPtr(gemNums,pos,gf);
	int nextGemNums[7];
	long long result;
	int i;
	/* 枝刈り(と見せかけて実装を楽にする) */
	if(gf && pos>=targetLength)return 0;
	/* メモを引く */
	memo=getMemoPtr(gemNums,pos,gf);
	if(*memo>0)return (*memo)-1;
	/* 次に使うために宝石の数をコピー */
	for(i=0;i<7;i++)nextGemNums[i]=gemNums[i];
	/* パターン数を初期化(今のパターンを数えるため、1を代入) */
	result=1;
	/* 次につながるパターンの数を加える */
	for(i=0;i<7;i++) {
		/* 辞書順で求められている宝石パターンを越える場合、終了 */
		if(gf && i>targetPuttern[pos])break;
		/* 次のパターンの数を数えて加える */
		if(nextGemNums[i]>0) {
			nextGemNums[i]--;
			result+=tansaku(nextGemNums,pos+1,gf && (i==targetPuttern[pos]));
			nextGemNums[i]++;
		}
	}
	/* メモに書き込んで結果を返す */
	*memo=result+1;
	return result;
}

int main(int argc,char* argv[]) {
	char gems[20];
	char target[20];
	int gemsCount[7]={};
	int i;
	FILE* fp;
	/* 引数の数のチェック */
	if(argc!=3) {
		fputs("Usage: gemstring <gems> <target>\n",stderr);
		fputs("set filename \"-\" to use standard input,\n",stderr);
		return 1;
	}
	/* 入力の読み込み */
	/* ファイル名に"-"を指定すると、標準入力から読み込む */
	if(argv[1][0]=='-' && argv[1][1]=='\0') {
		scanf("%s",gems);
	} else {
		fp=fopen(argv[1],"r");
		if(fp==NULL) {
			fputs("gems file open error!\n",stderr);
			return 1;
		}
		fscanf(fp,"%s",gems);
		fclose(fp);
	}
	if(argv[2][0]=='-' && argv[2][1]=='\0') {
		scanf("%s",target);
	} else {
		fp=fopen(argv[2],"r");
		if(fp==NULL) {
			fputs("target file open error!\n",stderr);
			return 1;
		}
		fscanf(fp,"%s",target);
		fclose(fp);
	}

	/* 入力のデータ化 */
	for(i=0;gems[i];i++) {
		if(gems[i]<'a' || 'g'<gems[i]) {
			fputs("Error : unsupported gems!\n",stderr);
			return 1;
		}
		gemsCount[gems[i]-'a']++;
	}
	for(i=0;target[i];i++) {
		if(target[i]<'a' || 'g'<target[i]) {
			fputs("Error : unsupported target!\n",stderr);
			return 1;
		}
		targetPuttern[i]=target[i]-'a';
	}
	targetLength=i;

	/* 計算 */
	printf("%lld\n",tansaku(gemsCount,0,1));

	return 0;
}