快速乘 （牛客 电音之王）

2019-04-14 15:46发布

站内文章 / 模拟电子
16466 0 1595
题目链接：https://ac.nowcoder.com/acm/contest/205/B   不会写。。。 记住板子吧。。 #include #include #include #include using namespace std; typedef long long LL; typedef unsigned long long u64; typedef __int128_t i128; typedef __uint128_t u128; struct Mod64 { Mod64():n_(0) {} Mod64(u64 n):n_(init(n)) {} static u64 init(u64 w) { return reduce(u128(w) * r2); } static void set_mod(u64 m) { mod=m; assert(mod&1); inv=m; for(int i=0;i<5;i++) inv*=2-inv*m; r2=-u128(m)%m; } static u64 reduce(u128 x) { u64 y=u64(x>>64)-u64((u128(u64(x)*inv)*mod)>>64); return LL(y)<0?y+mod:y; } Mod64& operator += (Mod64 rhs) { n_+=rhs.n_-mod; if (LL(n_)<0) n_+=mod; return *this; } Mod64 operator + (Mod64 rhs) const { return Mod64(*this)+=rhs; } Mod64& operator -= (Mod64 rhs) { n_-=rhs.n_; if (LL(n_)<0) n_+=mod; return *this; } Mod64 operator - (Mod64 rhs) const { return Mod64(*this)-=rhs; } Mod64& operator *= (Mod64 rhs) { n_=reduce(u128(n_)*rhs.n_); return *this; } Mod64 operator * (Mod64 rhs) const { return Mod64(*this)*=rhs; } u64 get() const { return reduce(n_); } static u64 mod,inv,r2; u64 n_; }; u64 Mod64::mod,Mod64::inv,Mod64::r2; //a*b%p 的防止超ll限度的写法 u64 pmod(u64 a,u64 b,u64 p) { u64 d=(u64)floor(a*(long double)b/p+0.5); LL ret=a*b-d*p; if (ret<0) ret+=p; return ret; } //Mod64::set_mod(M); //模设定 //Mod64 a(_a); //定义，初始化 //_a = a.get(); //转数值 //用%llu输入输出 //定义 u64; int main() { int T; scanf("%d",&T); while(T--){ u64 a0_,a1_,m0_,m1_,c_,M_; int k; scanf("%llu%llu%llu%llu%llu%llu%d",&a0_,&a1_,&m0_,&m1_,&c_,&M_,&k); Mod64::set_mod(M_); Mod64 a0(a0_),a1(a1_),m0(m0_),m1(m1_),c(c_),M(M_),ans(1),x(0); ans=ans*a1*a0; for(int i=2;i<=k;i++){ x=m0*a1+m1*a0+c; ans=ans*x; a0=a1; a1=x; } printf("%llu ",ans.get()); } }  

热门文章