蓝桥杯每日一题

#include <stdio.h>

//定义常量
#define N 100010
#define maxn 100000
#define MOD 998244353

//声明数组
int fact[N], infact[N]; //fact用于储存阶乘相关值，infact用于储存阶乘的逆元相关值
int pw[N];//用于储存10的幂次方相关值

//快速幂函数
int qp(int a, int n)
{
  int res = 1;
  while(n)
  {
    if (n & 1)
    {
      res = (long long)res * a % MOD;
    }
    n >>= 1;
    a = (long long)a * a % MOD;
  }
  return res;
}
// 功能：快速计算a的n次幂对MOD取模的结果
// 原理：利用二进制优化计算，n & 1用于判断n的二进制最低位是否为1，如果是，则将当前的a累乘到结果res中，然后n>>=1右移一位，同时a = a * a % MOD 对a进行平方取模，这样一直迭代，直到n变为0

//组合函数
int comb(int a, int b)
{
  if (a < 0 || b < 0 || a < b)
  {
    return 0;
  }
  return (long long)fact[a] * infact[a-b] % MOD * infact[b] % MOD;
}
// 功能：计算组合数C(a, b),即从a个元素中选b个元素的组合情况数，结果对MOD取模
// 实现：根据组合数公式C(a, b) = a! / (b! * (a - b)!)，利用预处理得到的fact（阶乘）和infact（阶乘逆元）数组来计算组合数。

//预处理函数
void Prework()
{
  pw[0] = 1;
  for (int i = 1; i <= maxn; i++)
  {
    pw[i] = (long long)pw[i - 1] * 10 % MOD;
  }
  fact[0] = 1;
  for (int i = 1; i <= maxn; i++)
  {
    fact[i] = (long long)fact[i - 1] * i % MOD;
  }
  infact[maxn] = qp(fact[maxn], MOD - 2);
  for (int i = maxn; i >= 1; i--)
  {
    infact[i - 1] = (long long)infact[i] * i % MOD;
  }
}
// 功能：对pw，fact，infact三个数进行初始化
// 实现：初始化pw数组，pw[i]表示10的i次幂对MOD取模的值，通过递推得到
//      初始化fact数组，fact[i]表示i的阶乘对MOD取模的值，通过递推得到
//      初始化infact数组，利用qp计算fact[maxn]的逆元（根据费马小定理，a的逆元为a^(MOD-2))，然后通过递推得到其他位置的阶乘逆元

//求解函数
void Solve()
{
  int n, m;
  scanf("%lld %lld", &n, &m);
  int res = 0;
  for (int i = m; 4 * i <= n; i++)
  {
    int t = (long long)comb(i, m) * comb(n - 3 * i, i) % MOD * pw[n - 4 * i] % MOD;
    if ((i - m) & 1)
    {
      res = (res - t + MOD) % MOD;
    }
    else
    {
      res = (res + t) % MOD;
    }
  }
  printf("%lld\n", res);
}
// 功能：用公式去求解
// 实现：使用位运算&判断(i-m)是否为奇数，结果为1是奇数，为0是偶数

int main()
{
  Prework();
  Solve();
  return 0;
}