T1-集合题解

前置知识

1.对于一个整数你，共有(2^n − 1)个非空子集.子集和的取值范围是[1,n(n+1)/2]。

2.

本题

可以求每一种子集和的方案数，然后枚举子集和𝑥，我们又知道子集和的方案数 𝑦，那么根据题意全部相乘就是x^y（可以用快速幂计算）.然后遍历子集和，将每一个x^y相乘取模即可。

问题一：

求每一个子集和的方案数，这里我们采用动态规划的思想。使用两重循环，外层循环遍历每个元素i，内层循环遍历子集和 j，从大到小更新 dp[j] 的值。dp[j] 的新值等于原来的 dp[j] + dp[j - i]。表示当前子集和为 j 的方案数等于不包含当前元素的子集和的方案数加上包含当前元素的子集和的方案数。 循环结束后，dp 数组中保存了每个子集和的方案数。

问题二：

由于 𝑛 较大的时候，x^y可能会超出 long long。但是我们发现x^y与998244353互质，那么运用费马小定理就可以解决，直接让方案数dp[i]%(mod-1)即可。

最后

用快速幂计算相乘就Ac了

代码：

```#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long dp[100001];
inline long long qpow(long long a, long long q){
    long long ans = 1;
    while(q){
        if(q&1)
            (ans *= a) %= mod;
        a=a*a%mod;
        q >>= 1;
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);        
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
    	for(int j = i*(i+1)/2; j >= i; j--){
        	(dp[j] = dp[j]+dp[j-i])%=(mod-1);
		}
	}
    long long ans = 1; 
    for(int i = 1; i <= n*(n+1)/2; i++)
        (ans *= qpow(i, dp[i])) %= mod;
    printf("%lld\n", ans);
    return 0;
}