思路:dp+思维
样例解释:
<=10的素数都有 2,3,5,7
所以可选的数为
2 3 5 7 4 9 8
选0个数(不选,即为原数列) 方案数为1
选1个数 方案数为7
选2个数 所有方案为:(2,3)(2,5)(2,7)(4,3)(4,5)(3,5)(3,7)方案数为7
选3个数 方案为(2,3,5) 方案数为1
所以 1+7+7+1=16
思路:
题目意思是将n个数按一定排列,再置换,求所有可能不同排列的个数
根据上述解释可以想到把数列的置换就变成一个环
进而把问题转化为共有n个元素,将它分为m个集合,求每个集合元素个数的LCM可能出现的情况
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=1010; const int INF=0x3f3f3f3f; const int mod=10007; const double eps=1e-6; const double PI=acos(-1.0); int prime[N],cnt=0; //prime数组存放所以素数,cnt为素数个数 bool st[N]; //false为素数 void get_prime(int n){ for(int i=2;i<=n;i++){ if(!st[i]) prime[cnt++]=i; //把素数i存到prime数组中 for(int j=0;j<cnt&&i*prime[j]<=n;j++){ st[i*prime[j]]=true; //找到的素数的倍数不访问 if(i%prime[j]==0) break; //关键代码 } } } ll dp[N]; void solve(){ int n;cin>>n; get_prime(n); dp[0]=1; _for(i,cnt){ //枚举素数 per(j,n,prime[i]){ int tmp=prime[i]; while(tmp<=j){ dp[j]+=dp[j-tmp]; tmp*=prime[i]; } } } ll ans=0; rep(i,0,n) ans+=dp[i]; cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(0); cin.tie(0); #ifdef DEBUG freopen("F:/laji/1.in", "r", stdin); // freopen("F:/laji/2.out", "w", stdout); #endif // int t;cin>>t;while(t--) solve(); return 0; }