欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 >

黑暗爆炸OJ 3028. 食物 生成函数

发布时间：2023/12/4 38 豆豆
生活随笔 收集整理的这篇文章主要介绍了 黑暗爆炸OJ 3028. 食物 生成函数 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

传送门

文章目录

  • 题意：
  • 思考

题意：

思考

考虑将每个条件转换成生成函数：
(1)f1(x)=1+x2+...=11−x2(1)f_1(x)=1+x^2+...=\frac{1}{1-x^2}(1)f1​(x)=1+x2+...=1−x21​
(2)f2(x)=1+x=1−x21−x(2)f_2(x)=1+x=\frac{1-x^2}{1-x}(2)f2​(x)=1+x=1−x1−x2​
(3)f3(x)=1+x+x2=1−x31−x(3)f_3(x)=1+x+x^2=\frac{1-x^3}{1-x}(3)f3​(x)=1+x+x2=1−x1−x3​
(4)f4(x)=x+x3+...=x1−x2(4)f_4(x)=x+x^3+...=\frac{x}{1-x^2}(4)f4​(x)=x+x3+...=1−x2x​
(5)f5(x)=1+x4+...=11−x4(5)f_5(x)=1+x^4+...=\frac{1}{1-x^4}(5)f5​(x)=1+x4+...=1−x41​
(6)f6(x)=1+x+x2+x3=1−x41−x(6)f_6(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}(6)f6​(x)=1+x+x2+x3=1−x1−x4​
(7)f7(x)=1+x=1−x21−x(7)f_7(x)=1+x=\frac{1-x^2}{1-x}(7)f7​(x)=1+x=1−x1−x2​
(8)f8(x)=1+x3+x6+...=11−x3(8)f_8(x)=1+x^3+x^6+...=\frac{1}{1-x^3}(8)f8​(x)=1+x3+x6+...=1−x31​
将其乘起来，得：(1−x2)(1−x3)x(1−x4)(1−x2)(1−x2)(1−x)(1−x)(1−x2)(1−x4)(1−x)(1−x)(1−x3)\frac{(1-x^2)(1-x^3)x(1-x^4)(1-x^2)}{(1-x^2)(1-x)(1-x)(1-x^2)(1-x^4)(1-x)(1-x)(1-x^3)}(1−x2)(1−x)(1−x)(1−x2)(1−x4)(1−x)(1−x)(1−x3)(1−x2)(1−x3)x(1−x4)(1−x2)​
约分可得x(1−x)4\frac{x}{(1-x)^4}(1−x)4x​。
由广义二项式定理1(1−x)m+1=∑n≥0(n+mn)xn\frac{1}{(1-x)^{m+1}}=\sum_{n\ge 0}\binom{n+m}{n}x^n(1−x)m+11​=∑n≥0​(nn+m​)xn得x(1−x)4=∑n≥0(n+3n)xn+1=∑n≥1(n+2n−1)xn\frac{x}{(1-x)^4}=\sum_{n\ge0}\binom{n+3}{n}x^{n+1}=\sum_{n\ge1}\binom{n+2}{n-1}x^n(1−x)4x​=∑n≥0​(nn+3​)xn+1=∑n≥1​(n−1n+2​)xn，所以第nnn项的答案为(n+2n−1)=(n+23)=(n+2)(n+1)(n)6\binom{n+2}{n-1}=\binom{n+2}{3}=\frac{(n+2)(n+1)(n)}{6}(n−1n+2​)=(3n+2​)=6(n+2)(n+1)(n)​，取个逆元直接计算即可。

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=10007,INF=0x3f3f3f3f; const double eps=1e-6;string s;LL qmi(LL a,LL b) {LL ans=1;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);cin>>s;int sum=0;for(int i=0;i<s.length();i++) sum=sum*10+s[i]-'0',sum%=mod;sum+=2; sum%=mod;int a=sum,b=(sum-1+mod)%mod,c=(sum-2+mod)%mod;printf("%lld\n",1ll*a*b*c%mod*qmi(6,mod-2)%mod);return 0; } /**/

总结

以上是生活随笔为你收集整理的黑暗爆炸OJ 3028. 食物 生成函数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。