一个显然的想法:定义 $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;
}