CSP-S模拟5复盘
T1
题目描述
小 S 在和小 W 玩游戏！
小 S 有一个 n 阶排列 p1,p2,⋯,pn。小 S 和小 W 轮流操作，小 S 先手。每次操作时，玩家可以以任意顺序重排 p1,p2,⋯,pp1。如果一个玩家操作时发现 p1 和自己之前某次操作时的 p1 相同，那么这名玩家就会输掉游戏。
小 S 和小 W 都足够聪明，所以小 W 一眼就看出小 S 的这个排列是先手必胜的！为了公平，小 W 提出在所有 n 阶排列中随机一个作为初始排列。听到这个提议，小 S 决定先计算自己的胜率。他需要你帮忙计算所有 n 阶排列中有多少个是后手必胜的。
答案对 10^9+7 取模。
输入格式
第一行一个正整数 n。
输出格式
一行一个非负整数，表示后手必胜的排列数对 10^9+7 取模后的结果。
思路
先手必胜当且仅当p1不是p1~p1的最小值。
反之，先手操作后原来的p1肯定在长度为新的p1的前缀内，这样后手就能把原来的p1再换回来，先手就输了。如果满足条件，先手可以把长度为p1的前缀内的最小值换到开头，同理后手就输了。
枚举p1,设p1=k,答案为：
((n-k)!/((n-k)-(k-1))!)*(n-k)!
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,N=2e7+9;
int n;
int jc[N],inv[N];
int qp(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int C(int n,int m){
if (n<m) return 0;
return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
cin>>n;
jc[0]=1;
for (int i=1;i<=n;i++){
jc[i]=jc[i-1]*i%mod;
}
inv[n]=qp(jc[n],mod-2);
for (int i=n-1;i>=1;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
inv[0]=1;
int ans=jc[n-1];
for (int i=2;i<=n;i++){
ans=(ans+C(n-i,i-1)*jc[i-1]%mod*jc[n-1-(i-1)]%mod)%mod;
}
cout<<ans;
return 0;
}
T2
题目描述
小 S 喜欢研究数对。他最近对满足如下性质的数对 (a,b) 产生了兴趣：
σ(a)+σ(b)=σ(gcd(a,b))+σ(lcm(a,b))，其中 σ(k) 表示 k 的因数个数。
如果 (a,b) 满足以上性质，那么小 S 称其是好的。现在，小 S 希望你在使得 1≤a≤b≤n 的所有数对 (a,b) 中，求出其中好的数对的 σ(a)+σ(b) 之和。
输入格式
第一行一个正整数 n。
输出格式
一行一个非负整数，答案。
思路
当a<=b时，(a,b)是好的当且仅当a|b
所以问题变为统计：
∑ σ(a)+σ(b)
a∣b
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+9;
int n;
int f[N];
signed main()
{
cin>>n;
for (int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
f[j]++;
}
}
int ans=0;
for (int i=1;i<=n;i++){
ans+=f[i]*f[i];
ans+=(n/i)*f[i];
}
cout<<ans;
return 0;
}
T3，T4
滤过