PKU 1625: Censored!

ここまでひどい悪問も珍しい。問題のタイトルどおりCensored!されるべき悪問。

概要
とりあえずAho-Corasickでも書いてDPしてくださいね。あと、long longなんてものには入らないし答え最大で80桁越えるのでおとなしく多倍長使ってください。

一般人の発想
とりあえず多倍長だしJava使いたいな…

悪問たる根源：
入力には
32 50 10
、￥ウЖ┆q忏溴骁栝觌祉铒?
Β
驿?
馥?
癌ē?
く．?
く．铽
Β‘飒
ウq憝?
驿Γ飒
隘ルΒ°?

こんなケースがあるかもしれません。文字化けしているように見える？いや、これが入力ファイルです。

とりあえず普通にJavaで書くと'あ'されて落ちます。ここでC++に諦めるのが最善です。

Javaで無理やり通したコード(Timus Online JudgeでISOなんたらというヒントをもらったけどこれあまりにも本質的じゃないのにマイナーすぎるよねって)

import java.util.*;
import java.math.*;
import java.io.*;
 class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1")); 
		BigInteger dp[][]=new BigInteger[51][101];
		int conv[]=new int[256];
		int t[][]=new int[101][256];
		int mark[]=new int[101];
		int failed[]=new int[101];
		int par[]=new int[101];
		int ji[]=new int[101];
		int Q[]=new int[1000];
		int Qtop=0;
		int Qbottom=0;
		int now=0;
String L=reader.readLine();
		int a=Integer.parseInt(L.split(" ")[0]);
		int b=Integer.parseInt(L.split(" ")[1]);
		int c=Integer.parseInt(L.split(" ")[2]);
		for(int i=0;i<256;i++)conv[i]=-1;
		for(int i=0;i<101;i++)
			for(int j=0;j<256;j++)
				t[i][j]=-1;
		String str=reader.readLine();
		byte P[]=str.getBytes("ISO-8859-1");
		int p[]=new int[P.length];
		for(int i=0;i<P.length;i++)p[i]=(int)(P[i])+128;
		for(int i=0;i<P.length;i++)conv[p[i]]=i;
		for(int i=0;i<101;i++)
			for(int j=0;j<26;j++)
				t[i][j]=-1;
		par[0]=-1;
		now++;
		for(int i=0;i<c;i++){
			str=reader.readLine();
			byte [] in=str.getBytes("ISO-8859-1");
			int at=0;
			for(int j=0;j<in.length;j++){
				if(t[at][(int)(in[j])+128]==-1){
					t[at][(int)(in[j])+128]=now;
					par[now]=at;
					now++;
					ji[now-1]=(int)(in[j])+128;
					at=now-1;
				}else at=t[at][(int)(in[j])+128];
			}
			mark[at]=1;
		}
		failed[0]=-1;
		Q[Qbottom++]=0;
		while(Qbottom>Qtop){
		//	System.out.println(Qbottom+" "+Qtop);
			int at=Q[Qtop++];
			for(int i=0;i<256;i++){
				if(t[at][i]!=-1)Q[Qbottom++]=t[at][i];
			}
			if(at==0)continue;
			int T=ji[at];
			int At=at;
at=par[at];
			while(true){
				//at=par[at];
				if(at==-1){
					failed[At]=0;
					break;
				}
				at=failed[at];
				if(at==-1){
					failed[At]=0;
					break;
				}
				if(t[at][T]!=-1){
					failed[At]=t[at][T];
					break;
				}
			}
	//		System.out.println(At+" "+failed[At]);
		}
		//System.out.println("WOLF");
		failed[0]=0;
		for(int i=0;i<51;i++)
			for(int j=0;j<101;j++)
				dp[i][j]=BigInteger.ZERO;
		dp[0][0]=BigInteger.ONE;
		for(int i=0;i<b;i++){
			for(int j=0;j<now;j++){
				for(int k=0;k<a;k++){
					if(t[j][p[k]]==-1){
						int to=failed[j];
						int M=0;
						while(t[to][p[k]]==-1){
							if(to==0){
								to=-1;
								break;
							}
							to=failed[to];
						}
						int TO=to;
						while(TO>=0){
							if(t[TO][p[k]]!=-1&&mark[t[TO][p[k]]]==1)M=1;
							if(TO==0)break;
							TO=failed[TO];
						}
						if(to==-1)dp[i+1][0]=dp[i+1][0].add(dp[i][j]);
						else if(mark[t[to][p[k]]]!=1&&M!=1) dp[i+1][t[to][p[k]]]=dp[i+1][t[to][p[k]]].add(dp[i][j]);
					}else{
						int TO=j;
						int M=0;
						while(TO>=0){
							if(t[TO][p[k]]!=-1&&mark[t[TO][p[k]]]==1)M=1;
							if(TO==0)break;
							TO=failed[TO];
						}
						if(M!=1&&mark[t[j][p[k]]]!=1)dp[i+1][t[j][p[k]]]=dp[i+1][t[j][p[k]]].add(dp[i][j]);
					}
				}
			}
		}
		BigInteger ret=BigInteger.ZERO;
		for(int i=0;i<now;i++)ret=ret.add(dp[b][i]);
		System.out.println(ret.toString());
	}
}

鬼門はTest 23らしいです。