NOIP2018模拟赛 马拉松冰球赛

NOIP2018模拟赛 马拉松冰球赛

题目大意

% 　　给定 n , m n,m n,m，你需要求出 m m m 个数 ( a 1 , a 2 , … , a n ) (a_1,a_2,dots ,a_n) (a1​,a2​,…,an​)，满足 ∏ i = 1 2 m a i ⩽ n m , ∀ i ∈ [ 1 , 2 m ] ∩ Z , a i ∈ N ∗ , a i ∣ n prod_{i=1}^{2m}a_ileqslant n^m,\forall iin[1,2m]∩Z ,a_iin N^*,a_i|n i=1∏2m​ai​⩽nm,∀i∈[1,2m]∩Z,ai​∈N∗,ai​∣n

% 　　求可行的方案数。
　　数据范围　 1 ⩽ n ⩽ 1 0 9 , 1 ⩽ m ⩽ 100 1leqslant nleqslant 10^9,1leqslant mleqslant 100 1⩽n⩽109,1⩽m⩽100

题解

% 　　令 T T T 为所有 a i a_i ai​ 的乘积，可以发现，满足 T ⩾ n m Tgeqslant n^m T⩾nm 的方案数和满足 T ⩽ n m Tleqslant n^m T⩽nm 的方案数量相等。换句话说，我们可以考虑所有方案加上满足 T = n m T=n^m T=nm 的方案，然后除以二。
　　可以发现，若 n n n 的约数个数为 d ( n ) d(n) d(n)，则只考虑第二条的方案数量为 [ d ( n ) ] m [d(n)]^m [d(n)]m。那么现在我们只需要考虑如何求出满足 T = n m T=n^m T=nm 的情况即可。
　　既然所有 a i a_i ai​ 之积为 n m n^m nm，若 n n n 中只含有一个质因数 p p p，这说明所有 a i a_i ai​ 中含有的 p p p 的总数量，必然等于 n n n 中含有的 p p p 的数量，换言之，我们单独考虑每个质数 p p p ，若 n n n 中包含了 k k k 个 p p p，则贡献的方案数等于在 2 m 2m 2m 个位置放 k k k 个 p p p 的方案数。
　　然后我们来考虑第二条限制，这说明每个位置上放的质因数 p p p 的个数不能超过 k k k，这也决定了这部分内容不可能使用排列组合完成，必须使用动态规划。
　　我们考虑 f[i][j] texttt{f[i][j]} f[i][j] 表示在 i i i 个位置中放进 j j j 个数的方案数量。转移如下 f [ i ] [ j ] = ∑ t = w k × m f [ i − 1 ] [ t − w ] f[i][j]=sum_{t=w}^{ktimes m}f[i-1][t-w] f[i][j]=t=w∑k×m​f[i−1][t−w]

% 　　边界为 ∀ i ∈ [ 1 , 2 × m ] ∩ Z , f [ i ] [ 0 ] = 1 forall iin [1,2times m]∩Z ,f[i][0]=1 ∀i∈[1,2×m]∩Z,f[i][0]=1。时间复杂度为 T ( n ) = Θ ( n + d ( n ) × m × log ⁡ 2 n ) text T(n)=Theta(sqrt n+d(n)times mtimes log_2 n) T(n)=Θ(n ​+d(n)×m×log2​n)

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long mod=998244353;
ll ksm(ll a,ll b){ll ret=1;while(b){if(b&1) ret=ret*a%mod;a=a*a%mod; b>>=1;} return ret;
}
int f[3200];
ll put(int n,int m,int w){memset(f,0,sizeof f);f[0]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)f[j]=(f[j]+f[j-1])%mod;for(int j=n;j>w;j--)f[j]=(f[j]-f[j-w-1]+mod)%mod;} return f[n];
}
int main(){int n,m;scanf("%d%d",&n,&m);int d_num=1; ll ans=1;for(int i=2;(long long)i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0) cnt++,n/=i;d_num=d_num*(cnt+1);ans=ans*put(m*cnt,2*m,cnt)%mod;}}if(n>1) ans=ans*put(m,2*m,1)%mod,d_num=d_num*2;ans=(ksm(d_num,2*m)+ans)%mod*ksm(2,mod-2)%mod;printf("%lldn",ans);return 0;
}