「BZOJ1965」[Ahoi2005] SHUFFLE 洗牌
\[x*(2^m)\equiv l(mod~n+1)\]x在mod n+1下逆元是n/2+1
所以移项得\[x\equiv(n/2+1)^m*l(mod~n+1)\]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define eps 1e-6 #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll n,m,l,ine; ll mul(ll a,ll b,ll p) { ll ans=0; for(ll i=b;i;i>>=1,a=(a+a)%p) if(i&1)ans=(ans+a)%p; return ans; } ll qpow(ll a,ll b,ll p) { ll ans=1; for(ll i=b;i;i>>=1,a=mul(a,a,p)) if(i&1)ans=mul(ans,a,p); return ans; } int main() { n=read();m=read();l=read(); ine=n/2+1; ine=qpow(ine,m,n+1); printf("%lld",mul(ine,l,n+1)); return 0; } |
计数器 9854732
OI 课件=>
OI 课件=>
应该是 2在mod n+1下逆元是n/2+1