ZigZagK的博客
[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛(7)【Counting Good Arrays】题解
2022年8月12日 15:38
HDU
查看标签

题目概述

HDU7217

解题报告

一个显然的想法:定义 $f_{i,j}$ 表示放了 $i$ 位,第 $i$ 位为 $j$ 的方案数,那么:

$$ f_{i,j}=\sum_{d|j}f_{i-1,d} $$

由于这题要求二维前缀和,考虑先求一次前缀和:$f_{i,j}$ 表示放了 $i$ 位第 $i$ 位小于等于 $j$ 的方案数,那么:

$$ f_{i,j}=\sum_{k=1}^{j}f_{i-1,{\lfloor{j\over k}\rfloor}} $$

如果没有那个 $1$ ,我们就只需要用到 $m$ 除法分块中所有的节点,这样就可以把第二位状态降到 $O(\sqrt m)$ 。

考虑除了第一次之外都至少 $\times 2$ ,这样至多只会乘 $30$ 次,然后考虑如何统计贡献,其实就是考虑把这些 $\times k$ 的部分放进长度为 $n$ 的序列中,并且规定第一个位置前面的都删掉,其他位置为 $1$ ,最后求一遍前缀积得到要求的数组,这样考虑就能求出长度为 $[1,n]$ 的所有情况。

因此稍微改变一下 $f_{i,j}$ 的转移。初值 $f_{1,j}=j$ ,转移:

$$ f_{i,j}=\sum_{k=2}^{j}f_{i-1,{\lfloor{j\over k}\rfloor}} $$

并且 $i$ 最大只有 $30$ 。不难发现转移 $j$ 的时候也是进行除法分块,因此这个转移的复杂度和杜教筛是一致的,即 $O(m^{3\over 4})$ 。

因此复杂度为 $O(30m^{3\over 4})$ ,最后答案为:

$$ \sum_{i=1}^{30}{n\choose i}f_{i,m} $$

示例程序

略有卡常,改了下数组访问顺序就过了。

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxs=31622<<1,MOD=1e9+7,LOG=32;

int te,n,m,S;LL f[maxs+5][LOG];
int a[maxs+5],ID[2][maxs+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
#define P(x) ((x)<=S?ID[0][x]:ID[1][m/(x)])
int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);
        a[0]=0;S=sqrt(m);
        a[++a[0]]=m;ID[1][1]=a[0];
        for (int l=2,r;l<=m;l=r+1){
            r=m/(m/l);a[++a[0]]=m/l;
            a[a[0]]<=S?ID[0][a[a[0]]]=a[0]:ID[1][m/a[a[0]]]=a[0];
        }
        for (int i=1;i<=a[0];i++) f[i][1]=a[i];
        for (int j=a[0];j;j--){
            for (int i=2;i<LOG;i++) f[j][i]=0;
            for (int l=2,r;l<=a[j];l=r+1){
                r=a[j]/(a[j]/l);
                int x=P(a[j]/l),len=r-l+1;
                for (int i=2;i<LOG;i++)
                    f[j][i]=ADD(f[j][i],MUL(len,f[x][i-1]));
            }
        }
        int C=1,ans=0;
        for (int i=1;i<LOG && i<=n;i++){
            C=MUL(C,MUL(n-i+1,Pow(i,MOD-2)));
            ans=ADD(ans,MUL(C,f[P(m)][i]));
        }
        printf("%d\n",ans);
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!