题意: 给出一个长度为n的序列 n<=1000 ,存在一个置换。 按照置换规则重新变成1-n 需要多少次?
对于所有可能的对应关系,有多少种可能的排数?
例如 原序列是1 2 3
给出置换规则 1->2 2->3 3->1
1 2 3
2 3 1
3 1 2
1 2 3
我们发现,置换了3次就恢复原序列了。
分析:
感谢sunsetcolors大佬的思路, 我们可以把这个置换看做一个图, 那么我们可以发现,置换必定出先循环节
上面这个1 2 3 例子,置换的循环节就是3.也就是说,我们要恢复,需要3次 = 循环节长度。
再举个例子,例如 1->2->3->1 4->5 6->6 可以发现,循环节长度分别是 3 2 1 。 可以手算答案=6次
可以得出 ans=lcm(3,2,1)=6
那么就是把问题变成,分解n,有多少种不同的lcm。 为了不考虑损耗,采用质因子来分解配凑。
必定 pri^k1 + pri^k2 + .... pri^kn <= n
下面就是一个完全背包的经典问题
代码:
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma G++ optimize(1) #pragma G++ optimize(2) #pragma G++ optimize(3) #pragma G++ optimize("Ofast") #pragma G++ optimize("inline") #pragma G++ optimize("-fgcse") #pragma G++ optimize("-fgcse-lm") #pragma G++ optimize("-fipa-sra") #pragma G++ optimize("-ftree-pre") #pragma G++ optimize("-ftree-vrp") #pragma G++ optimize("-fpeephole2") #pragma G++ optimize("-ffast-math") #pragma G++ optimize("-fsched-spec") #pragma G++ optimize("unroll-loops") #pragma G++ optimize("-falign-jumps") #pragma G++ optimize("-falign-loops") #pragma G++ optimize("-falign-labels") #pragma G++ optimize("-fdevirtualize") #pragma G++ optimize("-fcaller-saves") #pragma G++ optimize("-fcrossjumping") #pragma G++ optimize("-fthread-jumps") #pragma G++ optimize("-funroll-loops") #pragma G++ optimize("-fwhole-program") #pragma G++ optimize("-freorder-blocks") #pragma G++ optimize("-fschedule-insns") #pragma G++ optimize("inline-functions") #pragma G++ optimize("-ftree-tail-merge") #pragma G++ optimize("-fschedule-insns2") #pragma G++ optimize("-fstrict-aliasing") #pragma G++ optimize("-fstrict-overflow") #pragma G++ optimize("-falign-functions") #pragma G++ optimize("-fcse-skip-blocks") #pragma G++ optimize("-fcse-follow-jumps") #pragma G++ optimize("-fsched-interblock") #pragma G++ optimize("-fpartial-inlining") #pragma G++ optimize("no-stack-protector") #pragma G++ optimize("-freorder-functions") #pragma G++ optimize("-findirect-inlining") #pragma G++ optimize("-frerun-cse-after-loop") #pragma G++ optimize("inline-small-functions") #pragma G++ optimize("-finline-small-functions") #pragma G++ optimize("-ftree-switch-conversion") #pragma G++ optimize("-foptimize-sibling-calls") #pragma G++ optimize("-fexpensive-optimizations") #pragma G++ optimize("-funsafe-loop-optimizations") #pragma G++ optimize("inline-functions-called-once") #pragma G++ optimize("-fdelete-null-pointer-checks") #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <map> #include <queue> #include <deque> #include <set> #include <stack> #include <cctype> #include <cmath> #include <cassert> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define INF 0x3f3f3f3f #define PI 3.14159265358979323846 #define esp 1e-8 #define int long long using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; int dir2[8][2]={{-1,-1},{-1,1},{1,-1},{1,1},{0,-1},{-1,0},{0,1},{1,0}}; template <typename _T> inline void read(_T &f) { f = 0; _T fu = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); } while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); } f *= fu; } template <typename T> void print(T x) { if (x < 0) putchar('-'), x = -x; if (x < 10) putchar(x + 48); else print(x / 10), putchar(x % 10 + 48); } template <typename T> void print(T x, char t) { print(x); putchar(t); } const int N=1005; int n; int a[N]; int tot; int pri[N]; int dp[N]; int prime() {//打素数表 a[0]=1; a[1]=1; for(int i=2;i<=n;i++) { if(a[i]==0) { pri[tot++]=i; for(int j=i*i;j<=n;j+=i) { a[j]=1; } } } return tot; } signed main() { scanf("%lld",&n); int m=prime(); dp[0]=1; //完全背包 for(int i=0;i<m;i++) { for(int j=n;j>=pri[i];j--) { int x=pri[i]; while(x<=j) { dp[j]+=dp[j-x]; x*=pri[i]; } } } int ans=0; for(int i=0;i<=n;i++) { ans+=dp[i]; } printf("%lld\n",ans); return 0; }