Pedestrian1's BLOG
0%

2022杭电多校七1007 hdoj7217 Counting Good Arrays

发表于

题意：对于一个数列，满足数列长度不超过，数列最大值不超过，且对于所有，满足的方案数

设为数组长度为，最后一个数为的方案数，那么答案是

首先固定观察性质，可以发现对于不同的质因子，在分配时并不相互影响，所以是一个关于的积性函数那么我们只要求

对于，相当于对所有，把个因子可重复得分给个位置（最后一个位置固定为），即可重组合数，所以对于单个的方案数是

一个简单的生成函数证明是考虑每个位置的因子个数，对于一个位置，方案数为任意个的方案数都是，那么一个位置的生成函数是，个的位置对应的生成函数就是，方案数就是

那么对于所有的方案数就是

现在求出了，就可以通过筛求出关于的前缀和，这里预处理质数处的总和时，可以发现虽然不能像单项式那样子计算，但实际是质数个数乘上（一句只要求质数处的和，一语惊醒梦中人），剩余部分就是普通的操作

求出了固定下的关于的前缀和，对再做一次前缀和就能得到答案所需的式子，此时太大了，但是！！！我们发现上面有一个式子

在时就是一个关于的多项式，又因为是积性函数，所以也是一个多项式，并且项数是级别的，那么我们就可以通过拉格朗日插值计算得到最终的答案，复杂度

比较怪的是这题，网络赛在长度n不需要求前缀和时，虽然那题并不需要插值（用插值就啦）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
//tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tr;
//__gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> qu;
//typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
const int N = 200005;
int n, m, k;
const ll mod = 1e9 + 7;

ll fpow(ll x, ll r)
{
    ll result = 1;
    while (r)
    {
        if (r & 1)result = result * x % mod;
        r >>= 1;
        x = x * x % mod;
    }
    return result;
}

namespace binom {
    ll fac[N], ifac[N];
    int __ = []
    {
        fac[0] = 1;
        for (int i = 1; i <= N - 5; i++)
            fac[i] = fac[i - 1] * i % mod;
        ifac[N - 5] = fpow(fac[N - 5], mod - 2);
        for (int i = N - 5; i; i--)
            ifac[i - 1] = ifac[i] * i % mod;
        return 0;
    }();

    inline ll C(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }

    inline ll A(int n, int m)
    {
        if (n < m || m < 0)return 0;
        return fac[n] * ifac[n - m] % mod;
    }
}
using namespace binom;
namespace interpolate {
    ll f[N], pre[N], suf[N];

    ll lagrange(ll *f, int n, ll x)
    {
        if (x <= n)return f[x];
        ll ans = 0;
        pre[0] = x % mod;
        for (int i = 1; i <= n; i++)
            pre[i] = pre[i - 1] * (x - i + mod) % mod;
        suf[n + 1] = 1;
        for (int i = n; i; i--)
            suf[i] = suf[i + 1] * (x - i + mod) % mod;
        for (int i = 1; i <= n; i++)
        {
            ll res = ifac[i] * ifac[n - i] % mod * pre[i - 1] % mod * suf[i + 1] % mod * f[i] % mod;
            if ((n - i) & 1)res = mod - res;
            ans += res;
            if (ans >= mod)ans -= mod;
        }
        return ans;
    }
}
using namespace interpolate;

int vis[N];
ll prime[N];
int cnt;

void Prime(int n)
{
    cnt = 0;//多次时别忘了
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)break;
        }
    }
}

ll w[N], num_p[N], g[N];
int id1[N], id2[N];
int sz, t;
ll limit;

inline int getid(ll x)
{
    if (x <= sz)return id1[x];
    else return id2[limit / x];
}

void init(ll n)
{
    limit = n;
    sz = sqrt(n) + 5;
    Prime(sz);
    t = 0;//多次时别忘了，也可以设置成局部变量
    for (ll l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        w[++t] = n / l;
        num_p[t] = w[t] - 1;
        if (w[t] <= sz)id1[w[t]] = t;
        else id2[n / w[t]] = t;
    }
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= t && prime[i] * prime[i] <= w[j]; j++)
        {
            int id = getid(w[j] / prime[i]);
            num_p[j] = (num_p[j] - (num_p[id] - (i - 1)) % mod + mod) % mod;//质数个数
        }
}

ll S(ll n, int j, int r)
{
    if (prime[j] > n)return 0;
    ll ans = (num_p[getid(n)] - j + mod) * r % mod;
    for (int i = j + 1; i <= cnt && prime[i] * prime[i] <= n; i++)
        for (ll e = 1, sp = prime[i]; sp <= n; sp *= prime[i], e++)
            ans = (ans + C(e + r - 1, e) * (S(n / sp, i, r) + (e > 1))) % mod;
    return ans;
}

int main()
{
    int p, q, u, v, x, y, z, T;
    cin >> T;
    while (T--)
    {
        scanf("%d%d", &n, &m);
        init(m);
        for (int i = 1; i <= 35; i++)
            f[i] = (S(m, 0, i) + 1) % mod, f[i] = (f[i] + f[i - 1]) % mod;
        printf("%lld\n", lagrange(f, 35, n));
    }
    return 0;
}