A.Return

出题人大概是怕自己的中文十级没人知道，所以写了这么一个***题面。可能又觉得这题太水怕全场A掉后自己面子过不去，于是又故意把输出格式说的含糊不清。(鬼知道"那么输出-1"之前还用不用写Case啊)

直接排序去重，lowerbound找到有序数组里每个元素的位置统计答案即可。(考察知识：STL的熟练运用)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=10005;

typedef long long ll;

const ll mod=0x7fffffff;

int n;

ll a[N],b[N];

void work(int CASE)

{

	for(int i=1;i<=n;i++)

		scanf("%lld",&a[i]),b[i]=a[i];

	sort(b+1,b+n+1);

	int len=unique(b+1,b+n+1)-b-1,ans=0;

	if(len==1)

	{

		ans=-1;

		goto nxt;

	}

	for(int i=1;i<=n;i++)

	{

		int pos=lower_bound(b+1,b+len+1,a[i])-b;

		ll nxt,pre;

		if(pos==1)pre=b[len];

		else pre=b[pos-1];

		if(pos==len)nxt=b[1];

		else nxt=b[pos+1];

		if((pre+a[i])%mod==nxt)ans++;

	}

nxt:cout<<"Case #"<<CASE<<": "<<ans<<endl;

}

int main()

{

	int CASE=0;

	while(scanf("%d",&n)==1)

	{

		CASE++;

		work(CASE);

	}

	return 0;

}

B.One

把约瑟夫问题的递推式倒过来即可，$ans=(ans+i) \% (n-i+1)$。

至于柿子的含义？倒序枚举的i是第几轮，我们给每一轮剩下的人重新编号，已知最后幸存者的编号为1，那么就可以通过“每轮在幸存者上跳i次”的性质推出上一轮这个人的编号是几。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

using namespace std;

int T,n;

inline int read();

signed main()

{

//	freopen("in.txt","r",stdin);

//	freopen("1.out","w",stdout);

	T=read();

	while(T--)

	{

		n=read();

		int ans=1;

		for(int i=n;i;i--)

		{

			ans=(ans+i)%(n-i+1);

		}

		printf("%d\n",ans+1);

	}

}

inline int read()

{

	int s=0,f=1;char a=getchar();

	while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();}

	while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}

	return s*f;

}

C.Magic

这题如果不卡常还是不错的，考察知识非常综合，不过没什么思维含量就直接把欧拉定理lucas定理中国剩余定理费马小定理乘法逆元堆在一起就好啦。

当时看到$[gcd(i,N)==1]$虎躯一震，还以为要反演。其实直接暴力统计就行了。降幂的话可以欧拉定理对指数取模，不过$\varphi (p)$不是质数，所以求出在它的每一个质因子模意义下的答案后用CRT合并，质因子比较小所以要lucas防止出0。最后直接快速幂得到答案。

至于卡常……直接循环展开就行，还有就是枚举$i \in n$时可以只枚举到$\frac{n}{2}$，因为如果$gcd(i,n)\neq 1$,那么$gcd(i,n-i)\neq 1$也成立。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

#define re register

typedef long long ll;

const ll mod=54184622;

const ll phi=27092310;

const ll pr[6]={2,3,5,7,129011};

const int N=1000005;

ll fac[6][N],inv[6][N],t[6],m[6];

ll n,g;

inline ll qpow(ll a,ll b,ll p)

{

    ll res=1;

    while(b)

    {

        if(b&1)res=res*a%p;

        a=a*a%p;

        b>>=1;

    }

    return res;

}

inline ll gcd(ll x,ll y)

{

    if(!y)return x;

    return gcd(y,x%y);

}

inline ll C(ll x,ll y,int i)

{

    if(y>x)return 0;

    return fac[i][x]*qpow(fac[i][y],pr[i]-2,pr[i])%pr[i]*qpow(fac[i][x-y],pr[i]-2,pr[i])%pr[i];

}

ll lucas(ll x,ll y,int i)

{

    if(!y)return 1;

    return C(x%pr[i],y%pr[i],i)*lucas(x/pr[i],y/pr[i],i)%pr[i];

}

ll merge(ll x,ll y)

{

    if(y>x)return 0;

    ll res=0;

    ll val=lucas(x,y,0);

    (res+=val*m[0]*t[0])%=phi;

    val=lucas(x,y,1);

    (res+=val*m[1]*t[1])%=phi;

    val=lucas(x,y,2);

    (res+=val*m[2]*t[2])%=phi;

    val=lucas(x,y,3);

    (res+=val*m[3]*t[3])%=phi;

    val=lucas(x,y,4);

    (res+=val*m[4]*t[4])%=phi;

    return (res+phi)%phi;

}

int main()

{

    scanf("%lld%lld",&n,&g);

        fac[0][0]=1;

        for(re int j=1;j<=2;j++)

            fac[0][j]=fac[0][j-1]*1LL*j%pr[0];

        m[0]=phi/pr[0];

        t[0]=qpow(m[0],pr[0]-2,pr[0]);

        fac[1][0]=1;

        for(re int j=1;j<=3;j++)

            fac[1][j]=fac[1][j-1]*1LL*j%pr[1];

        m[1]=phi/pr[1];

        t[1]=qpow(m[1],pr[1]-2,pr[1]);

        fac[2][0]=1;

        for(re int j=1;j<=5;j++)

            fac[2][j]=fac[2][j-1]*1LL*j%pr[2];

        m[2]=phi/pr[2];

        t[2]=qpow(m[2],pr[2]-2,pr[2]);

        fac[3][0]=1;

        for(re int j=1;j<=7;j++)

            fac[3][j]=fac[3][j-1]*1LL*j%pr[3];

        m[3]=phi/pr[3];

        t[3]=qpow(m[3],pr[3]-2,pr[3]);

        fac[4][0]=1;

        for(re int j=1;j<=129011;j++)

            fac[4][j]=fac[4][j-1]*1LL*j%pr[4];

        m[4]=phi/pr[4];

        t[4]=qpow(m[4],pr[4]-2,pr[4]);

    ll tot=0;

    for(re int i=1;i*2<=n;i++)

        if(gcd(i,n)==1){

            (tot+=merge(g,i))%=phi;

            if(i*2!=n)

                (tot+=merge(g,n-i))%phi;

        }

    ll ans=qpow(n,tot,mod);

    cout<<ans<<endl;

    return 0;

}

巴特西

[NOIP模拟测试30]题解

A.Return

B.One

C.Magic

最新文章

热门文章