cdoj Dividing Numbers 乱搞记忆化搜索

//真tm是乱搞但是（乱搞的）思想很重要

解：大概就是记忆化搜索，但是原数据范围太大，不可能记下所有的情况的答案，于是我们就在记下小范围内的答案，当dfs落入这个记忆范围后，就不进一步搜索，直接返回记下来的答案，这样就起到了优化的效果，但是并不知道这种复杂度是怎么算的。然而我们由大到小排序，使得状态总可以很快地落入记忆化的范围。

dfs(n,now)代表[1..n]内不会被a[now]...a[k-1]整除的数有多少，那么答案就是dfs(n,0)。

转移关系如下:dfs(n,now)=dfs(n,now+1)-dfs(n/a[i],now+1)

之所以要-dfs(n/a[i],now+1)是为了避免一个数被重复减多次，能被整除的数整除后按大小排列一定是1,2,3,...,n/a[i],如果能被后面的数整除，就将其减去，也就是减dfs(n/a[i],now+1).

某学长的讲解：

给K个两两互素的数，问[1,N]中有多少个数不被K个数里任何一个数整除。

假设N比较小，可以这样做。dp[i][j]表示前i个素数，范围在[1,j]里的答案。那么，方程转移dp[i][j]=dp[i-1][j]+dp[i-1][j/p[i]]。（具体为啥仔细想想素数的性质，或者按照分解素数方法来想）

N很大，怎么办。当N<10万，20万，30万可以直接dp做。当N很大的时候，注意到j/p[i]，是log级别的，情况数并不会很多。所以可以设一个M，比如M=20万，当j<=M的时候，记忆化，O(1)查询，当j>M的时候，dfs搜索。

这题不好分析复杂度。可以发现，P数组里元素顺序是不影响答案的，我们可以把P从小到大排序，这样j/p[i]中的p[i]会更大，搜索起来更快。（当然，这只是小优化）。

不会写的话看代码。

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<queue>

 #include<vector>

 #include<map>

 #include<stack>

 #include<string>

 using namespace std;

 const int MAXN=;

 long long n;

 int k;

 int a[];

 long long f[MAXN][];

 bool cmp(int a,int b){

     return a>b;

 }

 long long dfs(long long n,int now){

     if (now>=k || n==) return n;

     if (n<MAXN && f[n][now]>=) return f[n][now];

     long long tmp=dfs(n,now+)-dfs(n/a[now],now+);

     if (n<MAXN) f[n][now]=tmp;

     return tmp;

 }

 int main(){

     scanf("%lld%d",&n,&k);

     for (int i=;i<MAXN;i++){

             for (int j=;j<k;j++){

                     f[i][j]=-;

             }

     }

     for (int i=;i<k;i++) scanf("%d",&a[i]);

     sort(a,a+k,cmp);

     printf("%lld\n",dfs(n,)); //printf("I64d printed\n");

     return ;

 }

 /*

 20 3

 2 3 5

 50 2

 15 8

 */

巴特西

cdoj Dividing Numbers 乱搞记忆化搜索

最新文章

热门文章