UPC12617 卡片

问题 D: 卡片

时间限制: 1 Sec  内存限制: 128 MB
提交: 51  解决: 19
[提交] [状态] [命题人:admin]

题目描述

你有一叠标号为1到n的卡片。
你有一种操作，可以重排列这些卡片，操作如下：
1.将卡片分为前半部分和后半部分。
2.依次从后半部分，前半部分中各取一张卡片，放到新的序列中。
例如，对卡片序列(1,2,3,4,5,6)操作后的结果为(4,1,5,2,6,3)。
现在你有一个初始为(1,2,3,⋯,n)的卡片序列，你需要求出进行m次操作之后第x个位置上的卡片的标号。

输入

第一行包含三个非负整数n,m,x。

输出

输出一行一个数，表示答案。

样例输入

复制样例数据

6 2 3

样例输出

6

提示

对于60%的数据，m≤107。
对于100%的数据，0≤n,m,x≤109。
数据有梯度，保证n为偶数。

这题是有循环节的，而且1e9的循环节很小才5e5。问m次操作后第x个数是多少，于是就想到了把本次循环跑完，把第x个数跑回他开始的位置就是第x个数的数值。

AC代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m,x;
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%(n+1);
        a=a*a%(n+1);
        b>>=1;
    }
    return ans;
}
unordered_map<int,int>mp;
int main()
{
    scanf("%lld%lld%lld",&n,&m,&x);
    int d=0;
    ll t=1;
    while(1)
    {
        t=t*2%(n+1);
        if(!mp.count(t))mp[t]=1;
        else break;
        d++;
    }//cout<<d<<endl;
    printf("%lld
",(x*qpow(2ll,d-m%d))%(n+1));
    return 0;
}