题解 | #集合#|背包与扩展欧拉定理
集合
https://ac.nowcoder.com/acm/contest/65193/A
直接对式子处理比较难。
注意到 ,而子集的所有取值为 级别的,可以考虑跑背包,把元素看作物品,求子集每种和的方案数 。
答案就是:
注意到背包求 要取模,由于是指数,不可以模 ,要使用扩展欧拉定理模 。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5;
const LL mod=998244353;
LL n,ans=1,num[N+5];
LL ksm(LL x,LL y)
{
LL ans=1;
while(y)
{
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
int main()
{
cin>>n;
num[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=i*(i+1)/2;j>=i;j--)
{
num[j]=(num[j]+num[j-i])%(mod-1);
}
}
for(int i=1;i<=n*(n+1)/2;i++)
{
ans=ans*ksm(i,num[i])%mod;
}
printf("%lld",ans);
}