数论——HYSBZ

题目链接

这道题可以发现一个规律，那就是牌x的位置

f[x]=x*2^m%(n+1)=l

也就是x*2^m≡l mod(n+1)

2^m与(n/2+1)^m在mod n+1 条件下互为逆元

所以x≡l*(n/2+1)^m

我们知道l，n，m，所以反手就是一个快速幂

不过这道题很坑，要用到快速乘，不然会TLE,PE,WA什么都有

题目代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long LL;
LL n,m,l;
LL ksc(LL a,LL b,LL mod){
    LL sum=0;
    while(b){
        if(b&1)sum=(sum+a)%mod;
        b>>=1;
        a=(a*2)%mod;
    }
    return sum;
}
LL quickpow(LL a,LL b,LL mod){
    LL ans=1;
    while(b){
        if(b&1)
            ans=ksc(ans,a,mod);
        b>>=1;
        a=ksc(a,a,mod);
    }
    return ans;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&l);
    LL t=quickpow(n/2+1,m,n+1);
    printf("%lld
",ksc(l,t,n+1));
    return 0;
}