公式求值

标题

公式求值

题目描述

算法设计

算法关键: 组数A[n]存放从1到n的阶乘值，运算时直接调用即可。把i的k次方存到一个临时变量，下一个i^k只需要temp*i

1. 把1到n的阶乘值依次存入A[n]
2. 直接循环累加即可

输入处理

    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    int A[n];//A[i]=(i+1)!

算法逻辑

1. 打印从1到n的阶乘表

       for (int i = 1; i <= n; ++i) {
           sum *= i;
           A[i - 1] = sum;
       }
   #ifdef DEBUG
       for (int i = 0; i < n; ++i) {
           printf("%d ", A[i]);
       }
       printf("\n");
   #endif
   

   条件编译语句内部是对应的输出语句，方便后续调试用的

2. 进行循环累加

       int ans = 0;
       for (int i = 1; i <= n; ++i) {
   #ifdef DEBUG
           printf("A[n-1]=%d,A[n-m-1]=%d,A[n-i-1]=%d,A[m-1]=%d,pow(i,k)=%d", A[n - 1], A[n - m - 1], A[n - i - 1],
                  A[m - 1], (int) pow(i, k));
           printf("\n");
   #endif
           ans += A[n - 1] * A[n - 1] * (int) pow(i, k) / (A[n - m - 1] * A[m - 1] * A[n - i - 1] * A[i - 1]);
       }
   

输出处理

    printf("%d", ans%999101);

调试运行

可以看到在第三次运行时由于i=n，在调用A[n-i-1]时数组下标越界

所以可以加一个缓冲量

让A[i]表示i！,A[0]初始化为1，这样既解决了下标越界的问题，也使接下来的读取更加简洁

打印A[i]修改为：

int A[n];//A[i]=i!
    A[0]=1;
    int sum = 1;
    for (int i = 1; i <= n; ++i) {
        sum *= i;
        A[i] = sum;
    }

后边的运算部分就可以把所有的-1都删掉了

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
#ifdef DEBUG
        printf("A[n]=%d,A[n-m]=%d,A[n-i]=%d,A[m]=%d,pow(i,k)=%d", A[n], A[n - m], A[n - i],
               A[m], (int) pow(i, k));
        printf("\n");
#endif

        ans += A[n] * A[n] * (int) pow(i, k) / (A[n - m] * A[m] * A[n - i] * A[i]);
    }

再次运行

得到了正确的结果

开开心心提交

果然难度不是吹的

一大半的运行时错误

这个算法有问题，因为计算10000！是不可能的

稍微化简一下

#include <stdio.h>
#include <math.h>

long long mul(int a, int b);

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += mul(n, n - i - 1) * mul(n, n - m + 1) * (long long) pow(i, k) / (mul(i, 2) * mul(m, 2));
    }
    printf("%lld", ans);
    return 0;
}

//计算(a-b)!
long long mul(int a, int b) {
    long long sum = 1;
    for (int i = b; i <= a; ++i) {
        sum *= i;
    }
    return sum;
}

还是运行时错误

看了下答案，麻了

import java.math.BigDecimal;
import java.util.Scanner;
public class Main {
    public final static BigDecimal P = new BigDecimal(999101);
    public final static BigDecimal TWO = new BigDecimal(2);
    public static long[] fac = new long[999101];
    public static long mod = 999101;
    public static long[][] dp = new long[1005][1005];
    public static BigDecimal n;
    public static BigDecimal m;
    public static int k;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = new BigDecimal(scanner.next());// n
        m = new BigDecimal(scanner.next());// m
        k = scanner.nextInt();// k
        if (n.equals(new BigDecimal(7349813)) && m.equals(new BigDecimal(3590741)) && k == 9)// 原题第四个数据貌似输出有误，正确应该输出为0
        {
            System.out.println(591101);
        } else {
            getfac(); // 预处理
            BigDecimal lc = Lucas(n, m);
            if (lc.compareTo(BigDecimal.ZERO) == 0) {
                System.out.println(0);
            } else {
                getdp();// 预处理系数
                long ans = 0l;// 最终值
                int i;
                long p = binpow(TWO, n.subtract(new BigDecimal(k))).toBigInteger().longValue();// 预处理2^(n-k)求模: 二项式定理
                for (i = k; i >= 0; i--, p = (p + p) % mod)
                    ans = (ans + dp[k][i] * p % mod) % mod;
                ans = ans * (lc.toBigInteger().longValue()) % mod;
                System.out.println(ans);
            }
            scanner.close();
        }
    }
    public static void getdp()// 计算系数求模
    {
        int i, j;
        dp[0][0] = 1l;
        long N = n.divideAndRemainder(P)[1].toBigInteger().longValue();// n % 999101
        for (i = 0; i < k; i++)
            for (j = 0; j < k; j++) {
                dp[i + 1][j] = (dp[i + 1][j] + (long) j * dp[i][j] % mod) % mod;
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (N + mod - (long) j) % mod * dp[i][j] % mod) % mod;
            }
    }
    // Lucas定理：组合数求模
    public static BigDecimal Lucas(BigDecimal n, BigDecimal m) {
        BigDecimal ret = BigDecimal.ONE;
        while (!n.equals(BigDecimal.ZERO) && !m.equals(BigDecimal.ZERO)) {
            int a = (n.divideAndRemainder(P))[1].intValue();
            int b = (m.divideAndRemainder(P))[1].intValue();
            if (a < b) {
                return BigDecimal.ZERO;
            }
            ret = ret
                    .multiply(new BigDecimal(fac[a] % mod))
                    .multiply(new BigDecimal(binpow(fac[a - b] * fac[b] % mod, mod - 2L)))
                    .divideAndRemainder(P)[1];
            n = n.divide(P, BigDecimal.ROUND_DOWN);
            m = m.divide(P, BigDecimal.ROUND_DOWN);
        }
        return ret;
    }
    // 预处理[0,P-1]的阶乘求模 0! 1！ 2！ 3! ..... 999100!
    public static void getfac() {
        int i;
        fac[0] = 1l;
        for (i = 1; i < mod; i++) {
            fac[i] = fac[i - 1] * (long) i % mod;
        }
    }
    // 模意义下取幂算法 -- 取模的运算不会干涉乘法运算
    // 大数快速取幂
    public static BigDecimal binpow(BigDecimal a, BigDecimal b) {
        a = a.divideAndRemainder(P)[1];
        BigDecimal res = BigDecimal.ONE;
        while (b.compareTo(BigDecimal.ZERO) > 0) {
            if (b.divideAndRemainder(TWO)[1].compareTo(BigDecimal.ONE) == 0)
                res = res.multiply(a).divideAndRemainder(P)[1];
            a = a.multiply(a).divideAndRemainder(P)[1];
            b = b.divide(TWO, BigDecimal.ROUND_DOWN);
        }
        return res;
    }
    // 普通数快速取幂
    public static long binpow(long a, long b) {
        a %= mod;
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
}

这种题需要很强的数学知识。。。

总结

人没了