#C240929A. 故事书

标签（Label）

数学推理

网址（Website）

题目详情 - 故事书 - Super

题解 - 故事书 - Super

题解（Solution）

AFO 小技巧 - WolfDeer

$d=0$ 时，原式为 $a^n mod\ p$ 。
$d=1$ 时，原式为 $(\Pi_{i=0}^{n-1}(a+i))mod\ p$ ，发现当 $a+i=p$ 的时候答案为 $0$ ，如果 $a+n<p$ ，得到的式子就可以用 $\frac{(a+n-1)!}{(a-1)!}$ 表示，花费 $O(p)$ 的时间预处理后可以直接 $O(1)$ 计算。
$d>1$ 时，原式很难计算，考虑将这种情况变成上述的两种情况，将原式变为 $d^n\Pi_{i=0}^{n-1}(a/d+i)$ 的形式，算出 $d$ 的逆元，按方法2中的方式计算即可。

出题者题解

【算法分析】

特判 $d=0$，则答案即为 $d^n\Pi_{i=0}^{n-1}(a/d+i)$ ，预处理阶乘及其逆元即可，时间复杂度 $O(Tlogp+p)$ 或 $O(T+p)$。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int A = 10123456;
const int N = 101234;
bool ST;

int bas[A],inv[A];
int n,a,d,p;

inline int ksm(int x,int k){
	int res = 1;while(k){
		if(k&1) res = res*x%p;
		x = x*x%p, k>>=1;
	}return res;
}


bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("story.in","r",stdin);
	freopen("story.out","w",stdout);
	int T=rd(),Tim = clock();p = rd();
	
	bas[0]=1;For(i,1,p-1) bas[i] = bas[i-1]*i%p;
	inv[p-1] = ksm(bas[p-1],p-2);
	Rof(i,p-1,1) inv[i-1] = inv[i]*i%p;
	assert(inv[1] == 1);
	
	while(T--){
		a=rd(), d=rd(), n=rd();
		if(!d) printf("%lld\n",ksm(a,n));
		else{
			a = a*inv[d]%p*bas[d-1]%p;
			if(a==0 || a+n>p) printf("0\n");
			else printf("%lld\n", ksm(d,n) * bas[a+n-1]%p * inv[a-1]%p);
		}
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}