Kickstart Round H 2018 A Big Buttons

简单，large数据用java大数

题目

Problem

You are a contestant on a popular new game show and are playing for the grand prize!

There are two big buttons, a red one and a black one. You will make a sequence of exactly N button presses.

There are lots of different sequences of presses you could make, but there are P forbidden prefixes, each of length no greater than N. If you make a sequence of presses which begins with any of the forbidden sequences, you will not win the grand prize. It is fine for your sequence to contain one or more forbidden prefixes as long as they do not appear at the start of your sequence.

A winning sequence must consist of exactly N button presses and must not begin with one of the forbidden prefixes. How many different winning sequences are there?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing two integers N and P, as described above. Then, there are P more lines, each of which contains a string of between 1 and N characters, inclusive, describing one of the forbidden sequences of presses. An R represents pressing the red button, whereas a B represents pressing the black button.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of winning sequences, as desribed above.

Limits

1 ≤ T ≤ 100. 1 ≤ P ≤ min(2N, 100). Each forbidden prefix is between 1 and N characters long, inclusive. No two forbidden prefixes will be the same.

Small dataset

1 ≤ N ≤ 10.

Large dataset

1 ≤ N ≤ 50.

Sample

Input 
 
4
3 2
BBB
RB
5 1
R
4 3
R
B
RBRB
50 5
BRBRBBBRBRRRBBB
BRBRBRRRBRRRBRB
BBBRBBBRBRRRBBB
BRBRBRRRBRRRB
BRBRBBBRBBBRB


output:

Case #1: 5
Case #2: 16
Case #3: 0
Case #4: 1125556309458944

Note that the last Sample case would not appear in the Small dataset.

In the first case, you must make a sequence of 3 presses. There are 8 possible sequences of three presses, but some of them will cause you to lose the game. They are listed below:

• RBB. This is forbidden since it starts with the first forbidden sequence (RB).

• RBR. This is forbidden since it starts with the first forbidden sequence (RB).

• BBB. This is forbidden since it starts with the second forbidden sequence (BBB).

Thus, there are only 5 winning sequences.

In the second case, you must make a sequence of 5 presses. There is only one forbidden sequence, which is R. This means that the first press must be B, and the next 4 presses can be either button. This gives a total of 16 different button presses.

In the third case, you must make a sequence of 4 presses. There are three forbidden sequences, but since every possible sequence begins with either R (the first forbidden sequence) or B (the second forbidden sequence), there are no winning sequences. So the answer is 0.

https://codejam.withgoogle.com/codejam/contest/3324486/dashboard#s=p0codejam.withgoogle.com

思路

由于只有R和B两种颜色的按钮，也就是，限制长度n，总共有 $2^n$ 种的排列方法。如：

input：
3 2
BBB
RB

output：
5

当n=3、p=2时，且序列开头的序列不能为BBB和RB。其中，开头包含BBB的序列只有一种，开头包含RB的序列有RBR、RBB两种。故 $8-3=5$ 种。

寻找规律可知：若序列长度为n，开头不能包含的序列长度为k，则，不符合要求的序列有： $2^{n-k}$ 个。

即： $8-2^{3-3}-2^{3-2}=8-1-2=5$ 。

但是，

4 3
R
B
RBRB

把第一个R套公式： $2^{4-1}=8$ ，这八种情况中包含RBRB，所以若把RBRB再套一次公式计算就重复减了。所以代码中要寻找，如果X字符串的首字母包含Y字符串，即

small.java

X.indexOf(Y)==0

那么不用考虑X字符串，只考虑短的Y字符串即可。因为Y字符串已经包含X字符串的情况。

最后，由于int的范围是 $2^{31}$ ，而large中，1 ≤ N ≤ 50。故将int改写成java大数即可。

small 题解

small.java

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException, IOException {
        Scanner cin = new Scanner(new FileReader("files/A-large-test.in"));
        PrintWriter cout = new PrintWriter(new FileWriter("files/A-large-test.out"));
        int w = cin.nextInt();
        for(int i=1;i<=w;i++){
            int n,p;
            int tot;
            n = cin.nextInt();
            p = cin.nextInt();
            tot = pow(n);

            String[] strings = new String[p+1];

            for (int j=1;j<=p;j++){
                strings[j] = cin.next();
            }

            for(int j=1;j<=p;j++){    //首字母包含另外一个字符串的，将该字符串设为0
                for(int k=1;k<=p;k++){
                    if(j==k){
                        continue;
                    }
                    if(strings[j].indexOf(strings[k])==0){
                        strings[j]="0";
                    }
                }
            }

            for (int j=1;j<=p;j++){
                if(!strings[j].equals("0")){
                    tot = tot-pow(n-strings[j].length());
                }
            }
            cout.println("Case #"+i+": "+tot);
        }
        cout.close();
        cin.close();
    }

    static int pow(int x){
        int tot = 1;
        for (int tmp=1;tmp<=x;tmp++){
            tot = tot*2;
        }
        return tot;
    }

}

large 题解（java大数）

large.java

import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException, IOException {
        Scanner cin = new Scanner(new FileReader("files/A-large-practice.in"));
        PrintWriter cout = new PrintWriter(new FileWriter("files/A-large-test.out"));
        int w = cin.nextInt();
        for(int i=1;i<=w;i++){
            int n,p;
            BigInteger tot;
            n = cin.nextInt();
            p = cin.nextInt();
            tot = pow(n);

            String[] strings = new String[p+1];

            for (int j=1;j<=p;j++){
                strings[j] = cin.next();
            }

            for(int j=1;j<=p;j++){
                for(int k=1;k<=p;k++){
                    if(j==k){
                        continue;
                    }
                    if(strings[j].indexOf(strings[k])==0){
                        strings[j]="0";
                    }
                }
            }

            for (int j=1;j<=p;j++){
                if(!strings[j].equals("0")){
                    tot = tot.subtract(pow(n-strings[j].length()));
                }
            }
            cout.println("Case #"+i+": "+tot);
        }
        cout.close();
        cin.close();
    }

    static BigInteger pow(int x){
        BigInteger tot = BigInteger.valueOf(1);
        for (int tmp=1;tmp<=x;tmp++){
            tot = tot.multiply(BigInteger.valueOf(2));
        }
        return tot;
    }

}