题目概述

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;
}