solution-code4763

2018-08-11

lolifamily

题解

生成函数

每种食物的生成函数

汉堡: $1 + 𝑥 2 + 𝑥 4 + \dots = 1 1 - 𝑥 2$

可乐: $1 + 𝑥 = 1 - 𝑥 2 1 - 𝑥$

鸡腿: $1 + 𝑥 + 𝑥 2 = 1 - 𝑥 3 1 - 𝑥$

蜜桃多: $𝑥 + 𝑥 3 + 𝑥 5 + \dots = 𝑥 1 - 𝑥 2$

鸡块: $1 + 𝑥 4 + 𝑥 8 + \dots = 1 1 - 𝑥 4$

包子: $1 + 𝑥 + 𝑥 2 + 𝑥 3 = 1 - 𝑥 4 1 - 𝑥$

土豆片炒肉: $1 + 𝑥 = 1 - 𝑥 2 1 - 𝑥$

面包: $1 + 𝑥 3 + 𝑥 6 + \dots = 1 1 - 𝑥 3$

乘在一起得到: $𝑓 (𝑥) = 𝑥 (1 - 𝑥) 4 = 𝑥 \cdot (1 - 𝑥) - 4$

带入广义二项式定理得 $𝑓 (𝑥) = 𝑥 \cdot \sum \infty 𝑖 = 0 𝐶 𝑖 𝑖 + 3 \cdot 𝑥 𝑖$

当 $𝑖 = 𝑛 - 1$ 时第 $𝑛 - 1$ 项为 $𝑥 \cdot 𝐶 𝑛 𝑛 + 2 \cdot 𝑥 𝑛 = 𝐶 3 𝑛 + 2 \cdot 𝑥 𝑛$

所以答案就为 $a n s = 𝑛 (𝑛 + 1) (𝑛 + 2) 6$

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define mod 10007
6
#define inv6 1668
7
using namespace std;
8
inline int GetInt()
9
{
10
  int ch,num=0;
11
  while(ch=getchar())
12
  {
13
    if(ch>='0'&&ch<='9')break;
14
  }
15
  while(ch>='0'&&ch<='9')
16
  {
17
    num=(num*10+ch-'0')%mod;
18
    ch=getchar();
19
  }
20
  return num;
21
}
22
int main(void)
23
{
24
  int n=GetInt();
25
  printf("%d\n",n*(n+1)%mod*(n+2)%mod*inv6%mod);
26
  return 0;
27
}