1 条题解
-
1
发现有和的限制，考虑构造生成函数。
答案就是第 项的系数。
然后考虑化简一下。
上面的部分比较简单，直接 枚举选择那些取 这一项，就可以计算出对应的 的指数与系数，现在考虑下面的怎么算。
构造一下。
考虑如何计算出 。
然后考虑将 带入为 。
结果发现其他项都变成了零。
$$\sum (c_i\prod_{i\ne j} (1-a_ja_i^{-1}))=(c_i\prod_{i\ne j} (1-a_ja_i^{-1}))=1 $$然后直接计算，得到
现在已知，考虑将前面的式子中的 展开。
于是变成
$$f(x)=(\prod (1-a_i^{b_i+1}x^{b_i+1}))(\sum c_i(1+a_ix+a_i^2x^2...)) $$这样的话，前面直接枚举，后面的系数可以直接算就做完了。
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=20,mod=998244353; int n,a[N],c[N],ans; ll b[N],m; int kuai(int a,ll b){ int ans=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod; return ans; } int main(){ scanf("%d%lld",&n,&m); for(int i=0;i<n;i++)scanf("%d%lld",&a[i],&b[i]); for(int i=0;i<n;i++){ int Inv=kuai(a[i],mod-2); c[i]=1; for(int j=0;j<n;j++)if(i!=j)c[i]=1ll*c[i]*(1+mod-1ll*a[j]*Inv%mod)%mod; c[i]=kuai(c[i],mod-2); } for(int i=0;i<1<<n;i++){ int ans1=1,ans2=0;ll sum=0; for(int j=0;j<n;j++)if(i&(1<<j))sum+=b[j]+1,ans1=1ll*ans1*(mod-1ll*kuai(a[j],b[j]+1)%mod)%mod; if(sum>m)continue; for(int j=0;j<n;j++)ans2=(ans2+1ll*c[j]*kuai(a[j],m-sum)%mod)%mod; ans=(ans+1ll*ans1*ans2%mod)%mod; } printf("%d",ans); }
- 1
信息
- ID
- 78
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
-
houzhiyuan