首页 > 专题系列 > Java解POJ > POJ 3708 Recurrent Function [解题报告] Java
2013
11-13

POJ 3708 Recurrent Function [解题报告] Java

Recurrent Function

问题描述 :

Dr. Yao is involved in a secret research on the topic of the properties of recurrent function. Some of the functions in this research are in the following pattern:

\begin{tabular} {ll} \textit{f}(\textit{j}) = \textit{a}$_j$ & for 1$\le$\textit{j}$<$\textit{d}, \\ \emph{f}(\emph{d}$\times$\emph{n}+\emph{j}) = d$\times$f(\textit{n})+\textit{b}$_j$ & for 0$\le$\textit{j}$<$\textit{d} and \textit{n}$\ge$1, \\ \end{tabular}

in which set {ai} = {1, 2, …, d-1} and {bi} = {0, 1, …, d-1}.
We denote:

\begin{tabular}{l}\emph{f}$_x$(\emph{m}) = \emph{f}(\emph{f}(\emph{f}($\cdots$\emph{f}(\emph{m})))) \quad\emph{x} times \\ \end{tabular}

Yao’s question is that, given two positive integer m and k, could you find a minimal non-negative integer x that

\begin{tabular}{l}\emph{f}$_x$(\emph{m}) = \emph{k}\\ \end{tabular}

输入:

There are several test cases. The first line of each test case contains an integer d (2≤d≤100). The second line contains 2d-1 integers: a1, …, ad-1, followed by b0, …, bd-1. The third line contains integer m (0<m≤10100), and the forth line contains integer k (0<k≤10100). The input file ends with integer -1.

输出:

For each test case if it exists such an integer x, output the minimal one. We guarantee the answer is less than 263. Otherwise output a word “NO”.

样例输入:

2
1
1 0
4
7
2
1
0 1
100
200
-1

样例输出:

1
NO

温馨提示:

For the first sample case, we can see that f(4)=7. And for the second one, the function is f(i)=i.

解题代码:

import java.util.*;
import java.math.*;
public class Main {
	static BigInteger x,y;
	static BigInteger[] a=new BigInteger[1000];
	static BigInteger[] m=new BigInteger[1000];
	static void egcd(BigInteger a,BigInteger b){
		if(b.equals(BigInteger.ZERO)){
			x=BigInteger.ONE;
			y=BigInteger.ZERO;
			return ;
		}
		egcd(b,a.mod(b));
		BigInteger temp=y;
		y=x.subtract((a.divide(b)).multiply(y));
		x=temp;
	}
	static BigInteger solve(int n){
		BigInteger M=BigInteger.ONE;
		BigInteger ans=BigInteger.ZERO;
		BigInteger mk=null;
		for(int i=0;i< n;i++)
			M=M.multiply(m[i]);
		for(int i=0;i< n;i++){
			mk=M.divide(m[i]);
			egcd(mk,m[i]);
			ans=ans.add(x.multiply(mk).multiply(a[i])).mod(M);
		}
		if(ans.compareTo(BigInteger.ZERO)<0)
			ans=ans.add(M);
		return ans;
	}
	static int[] a1=new int[1000];
	static int[] a2=new int[1000];
	static int[] m1=new int[1000];
	static int[] k1=new int[1000];
	static int[] w1=new int[1000];
	static int[] w2=new int[1000];
	static int[] w3=new int[101];
	static int[] w4=new int[101];
	static int[] w5=new int[101];
	static String mm;
	static String kk;
	static int prime(int x,int y){
		for(int i=2;x>1;i=i*i<=x?i+1:x)
			if(x%i==0){
				int k=0,p=1;
				while(x%i==0){
					x/=i;
					k++;
					p=p*i;
				}
				//System.out.println("w5[i]="+w5[i]+",i="+i+",p="+p+",y="+y);
				if(w5[i]!=0&&w3[w5[i]]%p!=y%p&&w3[w5[i]]%w5[i]!=y%w5[i])
					return 0;
				p=i;
				for(int j=1;j< k;j++){
					w4[p]=0;
					p*=i;
				}
				w3[p]=y%p;
				if(w5[i]< p)
					w5[i]=p;
			}
		return 1;
	}
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		while(true){
			int d=Integer.parseInt(in.next());
			if(d==-1)
				break;
			for(int i=1;i< d;i++)
				a1[i]=Integer.parseInt(in.next());
			for(int i=0;i< d;i++)
				a2[i]=Integer.parseInt(in.next());
			mm=in.next();
			kk=in.next();
			int l1=0,l2=0;
			BigInteger m2=new BigInteger(mm);
			while(!m2.equals(BigInteger.ZERO)){
				m1[l1++]=m2.mod(BigInteger.valueOf(d)).intValue();
				m2=m2.divide(BigInteger.valueOf(d));
			}
			BigInteger k2=new BigInteger(kk);
			while(!k2.equals(BigInteger.ZERO)){
				k1[l2++]=k2.mod(BigInteger.valueOf(d)).intValue();
				k2=k2.divide(BigInteger.valueOf(d));
			}
			if(l1!=l2){
				System.out.println("NO");
				continue ;
			}
			int q=a1[m1[l1-1]];
			int l=1;
			w1[0]=-1;
			boolean mark=true;
			for(int i=1;i<=d;i++){
				if(q==k1[l1-1]){
					w1[0]=i;
				}
				if(q==m1[l1-1]){
					w2[0]=l;
					break;
				}
				q=a1[q];
				l++;
			}
			if(w1[0]==-1){
				System.out.println("NO");
				mark=false;
				continue ;
			}
			for(int i=1;i< l1;i++){
				q=a2[m1[l1-1-i]];
				l=1;
				w1[i]=-1;
				for(int j=0;j<=d;j++){
					if(q==k1[l1-i-1]){
						w1[i]=j+1;
					}
					if(q==m1[l1-1-i]){
						w2[i]=l;
						break;
					}
					l++;
					q=a2[q];
				}
				if(w1[i]==-1){
					System.out.println("NO");
					mark=false;
					break;
				}
			}
			if(!mark)
				continue ;
			int num=0;
			for(int i=0;i<=d;i++){
				w3[i]=-1;
				w4[i]=1;
				w5[i]=0;
			}
			int tt=0;
			for(int i=0;i< l1;i++){
				if((tt=prime(w2[i],w1[i]))==0){
					mark=false;
					System.out.println("NO");
					break;
				}
			}
			if(!mark)
				continue ;
			for(int i=0;i<=d;i++)
				if(w3[i]!=-1&&w4[i]==1){
					a[num]=BigInteger.valueOf(w3[i]);
					m[num++]=BigInteger.valueOf(i);
					//System.out.println("i="+i+",w="+w3[i]);
				}
			if(num==0)
				System.out.println(1);
			else System.out.println(solve(num));
		}
	}

}

  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。