LG|LG P4161 [SCOI2009]游戏/LG P6280 [USACO20OPEN]Exercise G LGP4161[SCOI2009]游戏

Description(P4161) windy学会了一种游戏。
对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。
最开始windy把数字按顺序1，2，3，……，N写一排在纸上。
然后再在这一排下面写上它们对应的数字。
然后又在新的一排下面写上它们对应的数字。
如此反复，直到序列再次变为1，2，3，……，N。
如： 1 2 3 4 5 6
对应的关系为
1->2 2->3 3->1 4->5 5->4 6->6
windy的操作如下
1 2 3 4 5 6
2 3 1 5 4 6
3 1 2 4 5 6
1 2 3 5 4 6
2 3 1 4 5 6
3 1 2 5 4 6
1 2 3 4 5 6
这时，我们就有若干排1到N的排列，上例中有7排。
现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。
Description(P6280) Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 $N$ 头奶牛站成一排。对于$1\leq i \leq N$的每一个 $i$，从左往右第 $i$ 头奶牛的编号为 $i$。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。
给定长为 $N$ 的一个排列 $A$，奶牛们改变她们的顺序，使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i?$ 头。
例如，如果 $A=(1,2,3,4,5)$，那么奶牛们总共进行一步。如果 $A=(2,3,1,5,4)$，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：
0 步：$(1,2,3,4,5)$
1 步：$(3,1,2,5,4)$
2 步：$(2,3,1,4,5)$
3 步：$(1,2,3,5,4)$
4 步：$(3,1,2,4,5)$
5 步：$(2,3,1,5,4)$
6 步：$(1,2,3,4,5)$
求所有正整数 $K$ 的和，使得存在一个长为 $N$ 的排列，奶牛们需要进行恰好 $K$ 步。
由于这个数字可能非常大，输出答案模 $M$ 的余数（$10^8 \leq M \leq 10^9+7$，$M$ 是质数）。
Solution 两个问题，一个解法
两题的题目表述都表明题中给出的数的对应关系形成了一张图，这张图由多个环组成，可能有自环，环长之和为$N$
最终的答案分别是每个环长的$lcm$个数/和
对于一列数的$lcm$，等于这列数质因数分解后每个质数对应的最高次之积
所以现在要求将$N$分解，为了使分解后的数能组成更多种$lcm$，最优的选择应是让这列数互质
因为有可能分解出$1$，所以对于分解出$1$的个数不同，依次拆分$[1,N]$中所有数，输出它们的答案之和
考虑枚举质数
设$f_{i,j}$表示在前$i$个质数中，拆分数$j$所能得到的$lcm$个数/和
对于P4161：
$$f_{i,j}=\sum_{k=0}^{j\geq p_{i}^k} dp_{i-1,j-p_{i}^k}$$
对于P6280：
$$f_{i,j}=\sum_{k=0}^{j\geq p_{i}^k} dp_{i-1,j-p_{i}^k}\times p_{i}^k$$

文章图片

文章图片

#include #include using namespace std; int n,tot,prime[1005]; long long dp[1005],ans; bool vst[1005]; inline int read() { int w=0,f=1; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return w*f; } int main() { n=read(); for(int i=2; i<=n; i++) { if(!vst[i]) { prime[++tot]=i; } for(int j=1; j<=tot&&prime[j]*i<=n; j++) { vst[prime[j]*i]=true; if(!(i%prime[j])) { break; } } } dp[0]=1; for(int i=1; i<=tot; i++) { for(int j=n; j>=prime[i]; j--) { int temp=prime[i]; while(j>=temp) { dp[j]+=dp[j-temp]; temp*=prime[i]; } } } for(int i=1; i<=n; i++) { ans+=dp[i]; } printf("%lld\n",ans+1); return 0; }

游戏

文章图片

#include #include using namespace std; long long n,tot,prime[10005],mod; long long dp[10005],ans; bool vst[10005]; inline long long read() { long long w=0,f=1; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return w*f; } int main() { n=read(); mod=read(); for(long long i=2; i<=n; i++) { if(!vst[i]) { prime[++tot]=i; } for(long long j=1; j<=tot&&prime[j]*i<=n; j++) { vst[prime[j]*i]=true; if(!(i%prime[j])) { break; } } } dp[0]=1; for(long long i=1; i<=tot; i++) { for(long long j=n; j>=prime[i]; j--) { long long temp=prime[i]; while(j>=temp) { (dp[j]+=dp[j-temp]*temp)%=mod; temp*=prime[i]; } } } for(long long i=1; i<=n; i++) { (ans+=dp[i])%mod; } printf("%lld\n",(ans+1)%mod); return 0; }

Exercise G 【LG|LG P4161 [SCOI2009]游戏/LG P6280 [USACO20OPEN]Exercise G】