bzoj 3287: Mato的刷屏计划 高精水题 && bzoj AC150

3287: Mato的刷屏计划

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 124  Solved: 43
[Submit][Status]

Description

Mato同学喜欢上QQ，但是有少数傻逼总是问他一些弱智问题。Mato感到很反感，想要鄙视一下他们。他决定在QQ上刷屏，也就是发出一大堆字符。Mato的键盘上有4个键：A、B、C、D。按A就会输入一个字符，按B会把所有字符选中，按C会把选中的字符放入剪贴板，按D会插入剪贴板的内容。他的时间很宝贵，只能按n个键，你能告诉他最多能够输入多少字符吗？

Input

一个正整数n

Output

一个正整数，表示Mato所能输入的最多字符数。

Sample Input

7

Sample Output

9

HINT

Hint

n <= 1000000

样例1解释：Mato可以按AAABCDD，就可以输入9个字符。

注意此题中的粘贴与现实生活中有一定差别，不会覆盖选中的部分。

　　java水过，此题膜拜网上用FFT优化高精乘DP的大牛。

import java.io.IOException;

import java.util.Scanner;

import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException

    {

        // TODO Auto-generated method stub

        int arr[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

        int n;

        Scanner scanf= new Scanner(System.in);

        n=scanf.nextInt();

        if (n<)

        {

            System.out.println(arr[n]);

            scanf.close();

            System.exit();

        }else

        {

            int x=n%;

            x+=;

            BigInteger ans=new BigInteger("");

            BigInteger four = new BigInteger("");

            ans=BigInteger.valueOf(arr[x]);

            four=four.pow((n-x)/);

            ans=ans.multiply(four);

            System.out.println(ans);

        }

        scanf.close();

    }

}