D. Counting Factorizations #856 div2

编程入门 行业动态 更新时间:2024-10-23 19:30:26

D. Counting <a href=https://www.elefans.com/category/jswz/34/1072436.html style=Factorizations #856 div2"/>

D. Counting Factorizations #856 div2

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 <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;
} 
/* */

更多推荐

D. Counting Factorizations #856 div2

本文发布于:2024-03-14 19:58:21,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1737217.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:Factorizations   Counting

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!