【题解】B. Balls 的生成函数解法
[题目链接](https://ac.nowcoder.com/acm/contest/560/B)
# 题目大意
定义一个序列的权值为所有元素的乘积
求所有长度为 k 的正整数序列中,满足所有元素的和小于等于 S,把它们的权值加起来输出
答案模素数 p,其中
# 题解
设 表示长度为 i,和为 j 的答案,则:
生成函数为:
由于要求前缀和,再卷上 ,也就是:
因为:
所以:
卢卡斯定理一下就好了
# 题目大意
定义一个序列的权值为所有元素的乘积
求所有长度为 k 的正整数序列中,满足所有元素的和小于等于 S,把它们的权值加起来输出
答案模素数 p,其中
# 题解
设 表示长度为 i,和为 j 的答案,则:
生成函数为:
由于要求前缀和,再卷上 ,也就是:
因为:
所以:
卢卡斯定理一下就好了