Problem - 1794D - Codeforces

题意：

一个数分解质因数会变成这样的形式：

把所有的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

using namespace std;

#define int long long

typedef long long ll;

typedef pair PAII;

const int N=2e6+10,M=5050,INF=1e18,mod=998244353;

int fact[N],infact[N];

bool st[N];

int primes[N];

map mp;

int cnt;

vector 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

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 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<

}

return 0;

}

/*

*/

参考阅读

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。