题目详情:

用n个不同的字符（编号1 - n），组成一个字符串，有如下2点要求：

    1、对于编号为i 的字符，如果2 * i > n，则该字符可以作为最后一个字符，但如果该字符不是作为最后一个字符的话，则该字符后面可以接任意字符；

    2、对于编号为i的字符，如果2 * i <= n，则该字符不可以作为最后一个字符，且该字符后面所紧接着的下一个字符的编号一定要 >= 2 * i。

问有多少长度为M且符合条件的字符串。

例如：N = 2，M = 3。则abb, bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。

输入：n,m  (2<=n,m<=1000000000)；

输出：满足条件的字符串的个数，由于数据很大，输出该数Mod 10^9 + 7的结果。

函数头部

int validstring(int n,int m) {

}

代码如下：

 

import java.math.BigDecimal;import java.util.LinkedList;import java.util.Queue;public class Main {    public static int validstring(int n,int m) {        if (n > 2 || m > 1000000000){            System.err.println("‘n’或者‘m’超出范围了！");            return 0;        }        long count = countValid(n, m);        return BigDecimal.valueOf(count % (Math.pow(10, 9) + 7)).intValue();    }        //n个字符m位的全排列组合    private static long countValid(int n, int m) {        String v = "";        long s = 0;        char[] charArray = buildCharArray(n);        // 队列用来保存被访问节点的分支节点(邻接点）        Queue
    
      que = new LinkedList
     
      ();        que.offer(v);// 起点入队列        while (!que.isEmpty()) {            v = que.poll();// 弹出当前顶点            // 将当前节点的分支节(邻接）点加入到队列中            for (int i = 0; i < n; i++) {                String u = v + charArray[i];                if (u.length() == m) {//m位，则校验是不是符合题目的要求                    if (checkStr(u, charArray, 0)){                        System.out.println(u);                        ++s;                    }                } else{                    que.add(u); // 邻接点入队                }            }        }        return s;    }        //校验字符串是否符合规则    private static boolean checkStr(String str, char[] charArray, int j){        boolean returnFlag = false;        int n = charArray.length;        int m = str.length();        char c = str.charAt(j);        Integer i = getCharArrayIndex(charArray, c);        //如果2 * i > n，则该字符可以作为最后一个字符，但如果该字符不是作为最后一个字符的话，则该字符后面可以接任意字符；        if (2 * (i + 1) > n){            if (j == m - 1){                returnFlag = true;            }else{                returnFlag = checkStr(str, charArray, j + 1);            }        }else{//如果2 * i <= n，则该字符不可以作为最后一个字符，且该字符后面所紧接着的下一个字符的编号一定要 >= 2 * i。            if (j == m - 1){                returnFlag = false;            }else{                char d = str.charAt(j + 1);                int ii = getCharArrayIndex(charArray, d);                if (ii + 1 < 2 * (i + 1)){                    returnFlag = false;                }else{                    returnFlag = checkStr(str, charArray, j + 1);                }            }        }        return returnFlag;    }        private static Integer getCharArrayIndex(char[] charArray, char c){        Integer returnIndex = null;        for (int i = 0; i < charArray.length; i++){            char d = charArray[i];            if (d == c){                returnIndex = i;            }        }        return returnIndex;    }        //产生1-n的随机字符    private static char[] buildCharArray(int n){        StringBuffer returnValue = new StringBuffer();        for (int i = 0; i < n; i++){            char c = 'a';            c = (char)(c + i);            returnValue.append(c);        }        return returnValue.toString().toCharArray();    }    //start 提示：自动阅卷起始唯一标识，请勿删除或增加。     public static void main(String args[])     {            System.out.println(validstring(2, 10) + " 次");    }     //end //提示：自动阅卷结束唯一标识，请勿删除或增加。}