rt,题目
shaber lz`s code:
#include<iostream>
#include<algorithm>
#include<cmath>
#define exp 1e-10
using namespace std;
long long n,m,ans;
int x,y;
double tgt;
double pre[1000001];
void dfs(int num,int cnt,double sum){
if(sum>tgt+exp) return;
if(cnt==n){
if(abs(sum-tgt)<exp) ans++;
return;
}
if(num>m) return;
if(m-num+1+cnt<n) return;
if(sum+pre[m]-pre[m-(n-cnt)]>tgt+exp) return;
if(sum+pre[num+n-cnt-1]-pre[num-1]<tgt+exp) return;
dfs(num+1,cnt,sum);
dfs(num+1,cnt+1,sum+1.0/num);
}
int main(){
cin>>n>>m>>x>>y;
tgt=1.0*x/y;
dfs(1,0,0);
cout<<ans;
return 0;
}
思虑就是前缀和优化一个dfs