title: 贡献法+经典背包+费马小定理
categories:

  • ICPC
    tags:
  • null
    abbrlink: ‘3207e856’
    date: 2023-02-03 00:00:00

SDUT 校赛题目

Description

给定正整数 nn，计算 nn 个元素的集合 {1,2,⋯ ,n}\{1,2,\cdots,n\}，所有非空子集和的乘积取模 998 244 353998 \, 244 \, 353 后的结果。

Input

一个正整数 nn (1≤n≤200)(1\le n\le200)，代表集合大小。

例如 33 个元素的集合有 77 个非空子集，分别为 {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}，对子集内元素求和再乘积的结果就是

1×2×3×(1+2)×(1+3)×(2+3)×(1+2+3)=21601\times2\times3\times(1+2)\times(1+3)\times(2+3)\times(1+2+3)=2160

分析：本题关键在于我们不可能枚举所有子集，但我们考虑每个子集的贡献被限定在固定值域[l,r]，而值域不是很大，我们枚举x，l<=x<=r,看有多少个子集能够和为x，问题转化成背包求方案数。