课堂演示代码

dfs搜子集

搜索出每一种子集，第 $i$ 道选/不选，时间复杂度是 $O(2^n)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=21,mod=998244353;
int n,l,r,x,c[N];
ll ans,jie[N];
void dfs(int j,int cnt,int small,int big,int sum)
//搜到第j道题目，之前选择cnt道，之前最低分是small,最高分是big，总分sum 
{
	if(j>n)
	{
		if(cnt>=4&&small<=l&&big>=r&&sum>=x)ans=(ans+jie[cnt])%mod;
		return; 
	}
	dfs(j+1,cnt,small,big,sum);
	dfs(j+1,cnt+1,min(small,c[j]),max(big,c[j]),sum+c[j]);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>l>>r>>x;
	for(int i=1;i<=n;i++)cin>>c[i];
	jie[0]=1;
	for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
	//搜子集	
	dfs(1,0,1e9,0,0);	
	cout<<ans;
	return 0;
}