相信我，如果你什么东西不会，什么东西不懂，什么东西不记得了，就去尧神模板里找，相信我，你一定能找到！
#include#include #include #include #include #include using namespace std;#define ll long longll read(){ ll x=0,y=1;char ch=getchar(); while (isdigit(ch)){if (ch=='-')y=-1;ch=getchar();} while (!isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*y;}//exgcd求逆元，要求a,b互质ll exgcd(ll a,ll b,ll &x,ll &y){ if (b==0){ x=0,y=1; return a; } ll gcd=exgcd(b,a%b,x,y),tmp; tmp=x; x=y,y=tmp-a/b*y;}ll cal(ll a,ll b){ ll x,y; ll gcd=exgcd(a,b,x,y); if (1%gcd!=0) return -1; if (b<0)b=-1; x=(x%b+x)%b; while (!x) x+=b; return x;}/*利用费马小定理求逆元，当a,b互质，且b为质数时由费马小定理得,a^(b-1)=1(mod b)则有a*a^(b-2)=1(mod b)那么a^(b-2)就是a在mod b意义下的逆元*/ll inv(ll a,ll b){ ll ans=1; while (b){ if (b&1) ans*=a; a*=a;b>>=1; } return ans;}/*线性递推求逆元，要求p为奇素数设k=p%i,m=p/i,则有k+m*i=0(mod p)则-m*i=k两边同时除以k*i,有-m*inv[k]=inv[i]又有：(p-m)*inv[k]=m*inv[k](mod p)则：inv[i]=(p-p/i)*inv[p%i]%p*/ll inv[1000010];void getinv(){ inv[1]=1; for (ll i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;}