D. Counting Factorizations #856 div2
题意:
一个数分解质因数会变成这样的形式:
把所有的pi和ei放入一个可重集,给你一个可重集,问你原始的数有多少种可能
分析:
性质:底数只能是质数。底数只能有一个,指数可以有很多个
考虑dp
令为选了前i个数, 选了底数的个数为j的方案数
因为输入的为2*n,所以有n个为指数,n个为底数
对于当前枚举到的x来说,假设有y个
x分为两种情况:
第一种是只做指数,已经选了j个底数,假设一共操作了sum个数,所以有sum-j为指数,在剩下的没有操作过的位置上选择y个
第二种是x做一次底数的情况,其他y-1的情况全部作为指数
分步用乘,分类用加
所以这一步由上一步转移而来,用乘
两种不同的情况用加
这里介绍一个小tip
因为这个是二维的,所以必然要用到双重循环,看一下数据范围,二维的会超时,所以还需要优化一下。使用滚动数据,达到降维的效果。开一个类似于临时数组,相当于是这一步算好的情况,然后移到转移的数组上面,(相当于用这个临时数组作为中间数组),达到转移的效果。
这里我看到一篇博客很赞,贴个链接
C++ vector容器的swap方法(容器互换)_vector.swap_对的时间点的博客-CSDN博客
下面贴个这个题的代码:(整个题和代码的思路是看cup大佬qwq)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e18,mod=998244353;
int fact[N],infact[N];
bool st[N];
int primes[N];
map<int,int> mp;
int cnt;
vector<int> dp(N+10,0);
int qmi(int a, int k)
{
int res = 1;
while (k)
{
if (k & 1) res = res * a%mod ;
a = a * a%mod ;
k >>= 1;
}
return res;
}
void init(){
st[1]=1;
for (int i = 2; i <= N; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= N / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * qmi(i, mod - 2) % mod;
}
}
int C(int a,int b)
{
if(a<0||b<0||a<b) return 0;
return fact[a] * infact[b] % mod * infact[a - b] % mod;
}
signed main(){
IOS;
int T;
T=1;
//cin>>T;
init();
while(T--)
{
mp.clear();
int n;
cin>>n;
for(int i=1;i<=2*n;i++)
{
int x;
cin>>x;
mp[x]++;
}
dp[0]=1;
int sum=0;
for(auto it:mp)
{
int x=it.first,y=it.second;
vector<int> v(n+10,0);
for(int i=0;i<=n;i++)
{
v[i]+=(dp[i]*C(n-(sum-i),y))%mod;
if(i>=1&&!st[x]) v[i]+=(dp[i-1]*C(n-(sum-i+1),y-1))%mod;
}
dp.swap(v);
sum+=y;
}
cout<<dp[n]%mod;
}
return 0;
}
/*
*/