1 条题解

  • 2
    @ 2024-7-14 10:37:24

    这是 2023 年常州市 2+4 选拔原题,当时 n=2023n=2023

    原题的第一小题是求 a1+a2++ana_1+a_2+\cdots+a_n,那么我们不妨来求一下。

    注意到 i=1n(1+1i)\prod\limits_{i=1}^n(1+\dfrac1i) 这个式子,如果把 1+1i1+\dfrac1i 化成 i+1i\dfrac{i+1}i,则其等于 n+1n+1;若看作 nn 个二项式的乘积,则显然等于 1+a1+a2++an1+a_1+a_2+\cdots+a_n。因此 a1+a2++an=n.a_1+a_2+\cdots+a_n=n.\quad①

    那么回到这一题,也就是原题的第二小题。类似地,注意到 $\prod\limits_{i=1}^n(1-\dfrac1i)=1-a_1+a_2-a_3+\cdots=0$,即 a1a2+a3=1.a_1-a_2+a_3-\cdots=1.\quad②

    ±2\dfrac{①\pm②}2 可以求得题目要求的东西。

    由于 nn 很大,因此只要算一个 n±12\dfrac{n\pm1}2 的高精度即可。实现不难。

    #include<bits/stdc++.h>
    using namespace std;
    
    string s;
    int f,a[200005],ans[200005];
    
    int main()
    {
    	cin>>s>>f;
    	int n=s.size();
    	for(int i=0;i<n;i++) a[n-i]=s[i]-48;
    	if(!f)
    	{
    		int p=0;
    		while(!a[1+p]) a[1+p++]=9;
    		a[1+p]--;
    	}
    	else
    	{
    		int p=0;
    		while(a[1+p]>8) a[1+p++]=0;
    		a[1+p]++;
    	}
    	if(a[1]&1)
    	{
    		while(!a[n--]);n++;
    		for(int i=n;i;i--) cout<<a[i];
    		puts("/2");
    		return 0;
    	}
    	int r=0;
    	for(int i=n;i;i--)
    	{
    		int t=r*10+a[i];
    		ans[i]=t>>1;
    		r=t&1;
    	}
    	while(!ans[n--]);
    	n++;
    	for(int i=n;i;i--) cout<<ans[i];
    	return 0;
    }
    
    • 1

    信息

    ID
    1044
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    29
    已通过
    3
    上传者