西电校赛2022H题——朝歌夜雪

发表于2022-05-25更新于2022-05-25阅读次数

题意：

给你 n 个变量 c1,c2,...,cnc_1, c_2, ..., c_n ，现在让你往里放任意整数，要求

  1. ci−1∣cic_{i-1}|c_i
  2. 1≤ci≤C1 \leq c_i \leq C

给你 nn 和 CC ，问你有多少种放数的方案满足上述要求。答案模 998244353 。

样例：

1
2
3
4
5
6
7
8
input:
3 3
output:
7
input:
100000 100000
output:
502197289

这道题现场没敢写，首先感觉会不会是数论函数之类的题，那种我做不来。然后简单想了一下感觉像是组合数 dp ，这种我也不擅长，以前翻车过很多次，就直接弃疗了。考完看题解才发现其实我想得已经很接近了，只需要再坚持一下就能做出来。果然 ACM 最后一个小时一定不能松懈，坚持就是胜利啊 233 。

现场我想的时候总是拘泥于 C 的限制，所以不好做。也想过枚举最后一个数，但是考虑到 n 是 1e5 还是没继续想。其实枚举最后一个数之后复杂度就跟 n 无关了，可以直接公式算。

假设最后一个数为 p1q1p2q2...pkqkp_1^{q_1}p_2^{q_2}...p_k^{q_k} ，由于不同质因子之间完全独立的，所以可以一次只考虑一个质数幂因子，最后用乘法原理乘起来。

那么对于 piqip_i^{q_i} ，方案数其实就是把 qiq_i 个质因子分配到 n 个变量里的问题。用插板法，答案就是 C(n−1,qi+n−1)C(n-1, q_i+n-1) 。

计算组合数可以预处理 1 到 n+mn+m 的阶乘和阶乘的逆元，然后直接用组合数的阶乘公式算。复杂度是 O(CC)O(C\sqrt C) 。

注意不要测完 100000 100000 就 OK 了，记得手测边界情况（如 1 100000 ）。

代码：

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
#include<iostream>
#include<cstdio>
using namespace std;
int mo=998244353;
long long n,m;
long long prm[510000];
int prf[510000],prt=0;
long long jie[1100000];
long long rej[1100000];
void gtp(){
        for(int i=2;i<=m;++i){
                if(prf[i]==0)  prm[++prt]=i;
                for(int j=1;j<=prt && i*prm[j]<=m;++j){
                        prf[i*prm[j]]=1;
                        if(i%prm[j]==0)  break;
                }
        }
}
long long qcp(long long x,long long y){
        long long z=1;
        for(;y;y>>=1){
                if(y&1)  z=z*x%mo;
                x=x*x%mo;
        }
        return z;
}
void gtj(){
        jie[0]=1;
        rej[0]=1;
        for(int i=1;i<=n+m;++i){
                jie[i]=jie[i-1]*i%mo;
                rej[i]=qcp(jie[i],mo-2);
        }
}
inline long long C(int x,int y){
        return jie[y]*rej[x]%mo*rej[y-x]%mo;
}
inline long long ccl(int x){
        return C(n-1,x+n-1);
}
long long run(long long x){
        long long sum=1,cnt=0;
        for(int i=1;prm[i]*prm[i]<=x && i<=prt;++i){
                cnt=0;
                for(;x%prm[i]==0;x/=prm[i],cnt++);
                if(cnt>0)  sum=sum*ccl(cnt)%mo;
        }
        if(x>1)  sum=sum*ccl(1)%mo;
        return sum;
}
int main(){
        scanf("%lld%lld",&n,&m);
        gtp();
        gtj();
        long long ans=0;
        for(int i=1;i<=m;++i)  ans=(ans+run(i))%mo;
        printf("%lld\n",ans);
        return 0;
}