【BZOJ3028】食物(生成函数)
函数 生成
2023-09-11 14:14:41 时间
【BZOJ3028】食物(生成函数)
题面
一个人要带\(n\)个物品,共有\(8\)种物品,每种的限制分别如下:
偶数个;0/1个;0/1/2个;奇数个;
4的倍数个;0/1/2/3个;0/1个;3的倍数个。
求方案数。
\(n<=10^{500}\)
题解
对于八个物品的限制,分别构造生成函数,然后乘起来就是我们要的解。
化简后得到$$F(x)=\frac{x}{(1-x)4}=x(1+x+x2+...)^4$$
现在考虑求第\(n\)项系数。考虑第\(n\)项的组合意义,即将\(n\)划分为\(4\)个自然数的方案数。
所以第\(n\)项为\(C_{n+2}^3\),时间复杂度\(O(1)\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MOD 10007
#define INV 1668
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=(x*10+ch-48)%MOD,ch=getchar();
return x*t;
}
int main()
{
int n=read();
printf("%lld\n",1ll*n*(n+1)%MOD*(n+2)%MOD*INV%MOD);
return 0;
}
相关文章
- 飘逸的python - 实现一个pretty函数美丽的输出嵌套字典
- php一些高级函数方法
- Visual Studio 2017 - Windows应用程序打包成exe文件(2)- Advanced Installer 关于Newtonsoft.Json,LINQ to JSON的一个小demo mysql循环插入数据、生成随机数及CONCAT函数 .NET记录-获取外网IP以及判断该IP是属于网通还是电信 Guid的生成和数据修整(去除空格和小写字符)
- [复习]多项式和生成函数相关内容
- 【BZOJ3456】城市规划(生成函数,多项式运算)
- 【CF438E】The Child and Binary Tree(多项式运算,生成函数)
- PHP生成订单号函数
- 【CF891E】Lust 生成函数
- 【LOJ6077】「2017 山东一轮集训 Day7」逆序对 生成函数+组合数+DP
- 【BZOJ3771】Triple 生成函数+FFT
- 微信小程序端在函数组件中使用 mobx 注入 store 失败
- 腾讯测试高人分享4个关于 Python 函数(方法)的冷知识
- 阿里云发布函数计算 毫秒级弹性伸缩
- vue项目中定义全局变量、函数的几种方法
- JS-为句柄添加监听函数
- SARS病毒 (生成函数 + 快速幂)
- 《C++覆辙录》——2.11:运算符函数名字查找的反常行为
- oralce函数 STDDEV([distinct|all]x)
- 小知识随手记(十):多重重复解构对象、es6函数带默认参数时将生成声明作用域、一些注意点、动态设置getter/setter、mysql将字符串字段转为数字排序或比大小、pointer-events:none;属性
- HDOJ 2189 悼念512四川汶川大地震遇难者——来生一起走 【生成函数】
- 6.0 vue3 watch监听函数(reactive篇)
- Numpy随机数生成函数与常见分布函数解释
- mysql中生成指定区间内的真随机数函数rand()