NBUT1225 NEW RDSP MODE I(快速幂，规律)：

G - NEW RDSP MODE I

NBUT - 1225

题意：

​ 给你三个数 $n,$n, $m$m, $x$x。代表刚开始有 $1到n$1到n刚好n个数，现在让你将序列变换 $m$m次，问你变换 $m$m次之后前 $x$x个的值；

​ 序列每一次变换的规则：将其中奇数位置的数取出，按顺序放在最后面。

思路：

​ 因为变换的规则比较简单，所以我们可以根据这次位置 计算出 变换前的位置，向上推导 $m$m​次即可，那么我们可以先写出变换公式。

假设位置x变换前在位置last，那么我们不难推出下列公式：

• 如果 $x\&lt;=\lfloor n/2\rfloor$x<=⌊n/2⌋​ 则有 $last=2\ast x$last=2∗x​

• 否则 则有 $last=2\ast (x-\lfloor n/2\rfloor )-1$last=2∗(x−⌊n/2⌋)−1

这样规律显示的不够清楚，我们可以这样写

• 当n为偶数时候:

  • 如果 $x\&lt;=n$x<=n​，则有 $last=2\ast x$last=2∗x​.
  • 否则 $last=2\ast (x-n/2)-1=2\ast x-n-1$last=2∗(x−n/2)−1=2∗x−n−1​

• 当n为奇数的时候:

  • 如果 $x\&lt;=(n+1)/2$x<=(n+1)/2, 则有 $last=2\ast x$last=2∗x
  • 否则 $last=2\ast (x-(n+1\left)/2\right)-1$last=2∗(x−(n+1)/2)−1 即 $last=2\ast x-n$last=2∗x−n

​ 那么我们可以将位置 $x$x向上推导 $m$m次，最后得到的位置就是要求的位置 $x$x的值。但是 $m$m太大，这种根本不可行，我们现在试图找一个更好的公式。

​ 我们有没有发现一个规律，**当 $n$n​为奇数的时候 $last$last​ 可以表示为 $last=2\ast x\%n$last=2∗x %n​ ,(如果 $last=0$last=0​表示last=n)；**那么我们向上求 $m$m​次，则乘以 $2^m$2m​取余 $n$n​即可 (快速幂不难做到这一点)。但是当 $n$n​位偶数的时候怎么办呢？我们发现当 $n$n​位偶数时 $n个数$n个数​的结果与 $n+1$n+1​的结果一模一样。

因为第 $n+1$n+1​个数每次都是最后一个奇数，他总会放在最后面，不影响前 $n$n​个数的相对顺序

​ 所以我们当 $n$n​为偶数时，我们可以把 $n+1$n+1​变为奇数，然后位置 $x$x​的转换 $m$m​次前的位置为 $x\ast 2^m$x∗2m 。

所以程序思想分下面三步：

• 如果 $n$n为偶数就让 $n=n+1$n=n+1
• 转换 $m$m次后位置 $x$x的值为 $val=x\ast 2^m$val=x∗2m
• 如果 $val$val为 $0$0则输出 $n$n，否则输出 $val$val。

代码：

​

#include<queue>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int maxn=2e4+100;
int t;
ll quickPow(ll a,ll b,ll mod){
    ll ans=1ll;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll n,m,x,ans;
    while(cin>>n>>m>>x){
       if(n%2==0)   n++;
       ll mid=quickPow(2,m,n);
       for(ll i=1;i<=x;++i){
        if(i>1)
            cout<<" ";
         ans=i*mid%n;
         if(ans==0)
            cout<<n;
         else
            cout<<ans;
       }
       puts("");
    }
    return 0;
}