记第一次笔试

今天笔者参加了某大厂的笔试，第一题大致题目是这样的：

有一个整数n ( 1<=n<=1000000000)，最多有n个人组成队列，并从中选取一位当队长，求共可以组成多少队伍（其中队长不同视为不同的队伍比如( 1（队长）, 2 )和(1,2（队长）) ）表示不同的两个队伍。输出最多有多少个队伍对1000000007取模；

示例

输入

2

输出

4

分析队伍数分别为

(1) (2) (1,2) (1,2)其中斜体表示队长

我刚开始是这样分析的

若n = 3 时，队伍数就是

（1）（2）（3）（12）（12）（13）（13）（23）（23）（123）（123）（123）

于是我得出了一个结论：

三个选一个队长的选择只有一种

三个选两个队长的选择有两种

三个选三个队长的选择有三种

总数也就是 = 三个选一个 * 1 + 三个选两个 * 2 + 三个选三个 * 3

也就是

那么得出通项公式

问题就变成了求

因为

接下来我开始研究阶乘，最后终于把代码写好了，开开心心的填上去一运行，通过了0%的测试用例，我打开了IDEA进行调试发现当你= 100 是 抛出了 by/zero 的异常，原来当n很大时整数溢出最后导致阶乘结果为0，我将int改成了long，BigDecimal 还是存在问题，后来我转换思路看看能不能举例找出通项

n = 1   result = 1
n = 2   result = 4
n = 3   result = 12
n = 4   result = 32
n = 5   result = 80
...

果不其然我找到了规律

这样问题转换成了求2^(n-1)，我想起了位运算求2的幂次方，经过了一顿操作之后，我提交上去还是提示通过了0%的示例，同样当n足够大时还是溢出了。。。。不一会时间到了，我还没有来的及看第二题就结束了。

交卷之后我看了牛客网的帖子，有大牛说用快速幂就出来了，我去百度了一下什么是快速幂

https://blog.csdn.net/qq_40693171/article/details/84196079

首先要知道 （a * b）%c=（a%c）（b%c）*

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            long b = sc.nextLong();
            long c = 1000000007;
            long a = 2;
            long res = 1;
            a %= c;
            for (; b != 0; b /= 2) {
                if (b % 2 == 1)
                    res = (res * a) % c;
                a = (a * a) % c;
            }
            System.out.println(res);
        }
    }
}

后来我套了模板

import java.util.Scanner;

public class Alibaba {


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        System.out.println(fun2(x));
    }

    final static int M=1000000007;
    private static long fun1(int n){
        if(n==0) return 1;
        if(n==1) return 2;
        long ans=1;
        long base=2;
        while(n!=0){
            if((n&1)==1) ans=((ans%M)*(base%M))%M;
            base=((base%M)*(base%M))%M;
            n>>=1;
        }
        return ans%M;
    }
    //n*2^(n-1) % 1000000007
    private static int fun2(int n){
        return (int) (((n%M)*(fun1(n-1)%M))%M);
    }
}

调试未发现问题

通过这次笔试真的发现了自己与其他人差距甚大

coding everyday,everyday coding