算法分析

题目中求$a_1 + a_2 + … + a_{k} = n$，其中$n = g(x) = x^x mod 1000$，可以通过快速幂求出 $n$ ，时间复杂度是 $O(logn)$，同时可知 $mod 1000$ 后 $n$ 的范围一定最多是 $1000$

对于$a_1 + a_2 + … + a_{k} = n$，求正整数解的数量，可以通过隔板求出数量是 $C_{n - 1}^{k - 1}$，如图所示

又由于题目没有说要对 不定方程的正整数解组数 要取模，因此不能直接理性使用int或者long long去存，Java的同志可以使用BigInteger有毒的工具解决，需要大概估算$C_{n - 1}^{k - 1} $ 最大能取多大（能占多少位），根据数据范围，可以判断出最大值的上限是 $C_{1000}^{100} = \frac{1000!}{100! * 900!}$

按一下计算器：$\frac{1000!}{100! * 900!}$ = 6.3850511926305130236698511142022e+139，最多有139位，可以开150位长度的数组存组合数f[i][j]的值，因此需要开多一维存储f[i][j]对应的值，状态转移方程需要运行1000 * 100 = $10^5$ 次，每次转移计算的长度是 $150$ ，最多计算 $1.5 * 10^7$次

时间复杂度 $O(1000 * k * 150)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 150;
    static int[][][] f = new int[1000][100][N];

    static int qmi(int a, int k, int p)
    {
        long res = 1 % p;
        long t = a;
        while(k != 0)
        {
            if((k & 1) == 1) res = res * t % p;
            k >>= 1;
            t = t * t % p;
        }
        return (int)res;
    }

    //逆序存储
    static void add(int[] c, int[] a, int[] b)
    {
        for(int i = 0, t = 0;i < N;i ++)
        {
            t += a[i] + b[i];
            c[i] = t % 10;
            t /= 10;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        int x = scan.nextInt();

        int n = qmi(x, x, 1000);
        //C(n - 1, k - 1)
        for(int i = 0;i < n;i ++)
            for(int j = 0;j <= i && j < k;j ++)
            {
                if(j == 0) f[i][j][0] = 1;
                //f[i][j] = f[i - 1][j] + f[i - 1][j - 1]
                else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);
            }

        int[] g = f[n - 1][k - 1];
        //找到最高位i
        int i = N - 1;
        while(g[i] == 0) i --;
        while(i >= 0) System.out.print(g[i --]);
    }
}