当前位置：首页 > article >正文

2025.2.2牛客周赛 Round 79 IOI

article 2025/2/5 5:10:52

文章目录

2025.2.2牛客周赛 Round 79 IOI
- C小红的二叉树
- D小红的“质数”寻找
- - 代码
- E 小红的好排列 (排列组合)
- - 思路
  - 代码
- F小红的小球染色期望（前缀和，逆元）
- - 思路
  - 代码
- 总结

2025.2.2牛客周赛 Round 79 IOI

牛客周赛 Round 79 IOI

C小红的二叉树

推出公式 $3\times 2^{n-1}-5$

但是数据太大了，没有模幂函数，只能循环写

D小红的“质数”寻找

在【x，2x】之间找到一个数字，各个数位相加的和是一个质数。

由于此区间跨越较大，完全可以自己设计固定值，再加上数据10^18,想查找，筛法，对我来说完全做不到。

竟然错把9当作了质数，不嘻嘻

代码

void solve()
{
    string s;
    cin>>s;
    if(s[0]=='1')
    s[0]='2';
    else if(s[0]=='2')
    s[0]='3';
    else if(s[0]<'5')
    s[0]='5';
    else if(s[0]<'7')
    s[0]='7';
    else if(s[0]<'9')
    s[0]='9';
    else s[0]='1';
    fir(i,1,s.size()-1)
        s[i]='0';
    if(s[0]=='1')
        cout<<'1';
    cout<<s<<'\n';  
}

E 小红的好排列 (排列组合)

题目描述

$\hspace{15pt}$ 小红认为一个偶数长度为 n 的排列 {a1,a2,…,an} 是好排列，当且仅当恰好有一半的 i使得 $a_i \times i$ 是 3的倍数。小红想知道，全部长度为 n 的排列中，共有多少个好排列？由于答案可能很大，请将答案对10^9+7取模后输出。

长度为 n的排列是由 1∼n 这 n个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。

输入描述:

 在一行上输入一个正偶数 n (2≦n≦106) 代表排列中的元素数量。

输出描述:

输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对(10^9+7)取模后输出。

思路

理解题意可知有两种满足方式：位置处于3的倍数（定义为p），数值为3的倍数（定义为q）

只需将部分q放在非p位置，部分q放在p位置，其实就是保证q|p=n/2

首先定义两个变量x=n/2-n/3,y=n/3,分别表示需要几个q放在非p位置，有几个q。

接下来就看怎么排列

从y中选择x个放在非p位置： $C_{y}^{x}$
从非p位置选x个存放： $C_{n-y}^{x}$
P位置的可以随便移动： $A_{y}^{y}$
非p位置也可以随便移动： $A_{n-y}^{n-y}$

将以上式子相乘就是最终答案，要用乘法逆元的，不会写可以看求组合数（递推法、乘法逆元、卢卡斯定理、分解质因数）-CSDN博客，2024ccpc全国邀请赛（郑州）补题（乘法逆元）-CSDN博客

~~什么？运行超时？~~

~~可以求组合数时特判上>下，返回0，或者直接特判x>y,返回0.~~

起初没对有两个原因，一是没用乘法逆元，以为边乘边除就可以解决，若真是如此，那谁还用乘法逆元呀。二是式子列错了，多加了个 $A_{y-x}^{y-x}$ , 想着除移进来的非q，剩下p也可以随便移动，也知道可能会重复，但不知道该怎么列。其实转换一下思路就可以了，重点不在哪一部分数字，既然排列组合就该把某一类看作等同。

错误的：先排列p位置即求y的阶乘。再排列移动后剩余的y-x

正确的：先移动，再排列，移动x个数字后，再对p,非p进行全排列就涵盖所有。不管移走谁，都是q中的某个，组合完，移动，再分别全排列。

代码

int ans2=1;
const int N=1e8,mod=1e9+7;
int a[N];// 阶乘%mod
int qpow(int a,int b,int c)
{int ans=1;
    while(b)
    {
        if(b&1) ans= ans*a%c;
        a=a*a%c,b/=2;
    }return ans;
}
int C(int n,int m)//排列
{
    if(m>n) return 0;
    return a[n]*qpow(a[n-m]*a[m]%mod,mod-2,mod)%mod;
    //pow(a,b,c)  a^b过程中%c
}
signed main()
{
    int n;
    cin>>n;
     a[0]=1;
     for(int i=1;i<=n;i++)
     a[i]=i*a[i-1]%mod;
    int x=n/2-n/3,y=n/3;
    if(x>y) cout<<"0\n";
    else
    { 
         ans2=ans2*C(y,x)%mod; 
      ans2=ans2*C(n-y,x)%mod; 
     ans2=ans2*a[n-y]%mod*a[y]%mod; 
    cout<<ans2<<"\n"; 
    }
}

F小红的小球染色期望（前缀和，逆元）

题目描述

有 n 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作直到无法操作，请你计算小红操作次数的期望。

输入描述:

在一行上输入一个正整数 n(1≦n≦106) 代表小球数量。

输出描述:

可以证明答案可以表示为一个不可约分数，为了避免精度问题，请直接输出整数 $p×q^{−1} modM)$

思路

画几个小球，列式子就可以找到规律

数组a存放不同n值对应的答案

1 2 3 4 5 6 7

当你模拟以不同方式进行第一次操作，选择34时，接下来的数学期望是多少呢？

左边有两个小球，右边有三个，所以是a[2]+a[3]。式子如下

在这里插入图片描述

所以，这道题用逆元和前缀和就可以完成。

我的代码里，前缀和是在原a数组上覆盖的，只要保证a[n]是最终结果就行

代码

const int N=1e6+10,M=1e9+7;
int a[N];
int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%M;
        a=a*a%M;b/=2;
    }return ans;
}
void solve()
{
    int n;
    cin>>n;
    a[2]=1;
    fir(i,3,n)
    {
        a[i-1]=(a[i-1]*2+a[i-2])%M;
        a[i]=(a[i-2]*qpow(i-1,M-2)+1)%M;
    }
    cout<<a[n]<<'\n';
}