solution-code4763

2018-08-11

lolifamily

题解

生成函数

每种食物的生成函数

汉堡: $1 + x^{2} + x^{4} + \dots = \frac{1}{1 - x^{2}}$

可乐: $1 + x = \frac{1 - x^{2}}{1 - x}$

鸡腿: $1 + x + x^{2} = \frac{1 - x^{3}}{1 - x}$

蜜桃多: $x + x^{3} + x^{5} + \dots = \frac{x}{1 - x^{2}}$

鸡块: $1 + x^{4} + x^{8} + \dots = \frac{1}{1 - x^{4}}$

包子: $1 + x + x^{2} + x^{3} = \frac{1 - x^{4}}{1 - x}$

土豆片炒肉: $1 + x = \frac{1 - x^{2}}{1 - x}$

面包: $1 + x^{3} + x^{6} + \dots = \frac{1}{1 - x^{3}}$

乘在一起得到: $f (x) = \frac{x}{(1 - x)^{4}} = x \cdot (1 - x)^{- 4}$

带入广义二项式定理得 $f (x) = x \cdot \sum_{i = 0}^{\infty} C_{i + 3}^{i} \cdot x^{i}$

当 $i = n - 1$ 时第 $n - 1$ 项为 $x \cdot C_{n + 2}^{n} \cdot x^{n} = C_{n + 2}^{3} \cdot x^{n}$

所以答案就为 $ans = \frac{n (n + 1) (n + 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
}