还是太菜了 没有察觉到自己常数大。
可以简单的发现每个数字对答案的风险为 C(n-1,i-1).
对于模数为质数 显然可以卢卡斯定理。
对于模数不为质数 显然可以分解质因数使用扩展卢卡斯定理(分解质因数+求阶乘+exgcd+CRT.
const ll MAXN=1000010,maxn=11,N=400010;
ll n,mod,top,M,MM,xx,yy;
ll a[N];
ll w[maxn],p[maxn];
ll ans[maxn][N];
ll fac[MAXN];
inline void exgcd(ll a,ll b)
{
if(!b){xx=1;yy=0;return;}
exgcd(b,a%b);
ll zz=xx;xx=yy;yy=zz-a/b*yy;
}
inline ll get_c(ll x,ll xx,ll xxx)
{
ll cnt=0,ww=1;
while(x>=ww)
{
ww=ww*MM;
cnt+=x/ww;
cnt-=xx/ww;
cnt-=xxx/ww;
}
return cnt;
}
inline void prepare()
{
fac[0]=1;
rep(1,M,i)if(i%MM)fac[i]=fac[i-1]*i%M;
else fac[i]=fac[i-1];
}
inline ll ksm(ll b,ll p,ll mod)
{
ll cnt=1;
while(p)
{
if(p&1)cnt=cnt*b%mod;
p=p>>1;b=b*b%mod;
}
return cnt;
}
inline ll get_ans(ll a)
{
if(a<=MM)return fac[a];
return ksm(fac[M],a/M,M)%M*fac[a%M]%M*get_ans(a/MM)%M;
}
inline ll inv(ll a,ll b)
{
exgcd(a,b);
return (xx%b+b)%b;
}
inline ll solve(ll a,ll b)//求出 C(a,b)%M;
{
ll w1=get_c(a,b,a-b);
ll c1=get_ans(a);//求出a!%M
ll c2=get_ans(b);
ll c3=get_ans(a-b);
return c1*inv(c2,M)%M*inv(c3,M)%M*ksm(MM,w1,M)%M;
}
signed main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
get(n);get(mod);
rep(1,n,i)get(a[i]);
ll cc=mod;
for(ll i=2;i*i<=cc;++i)
{
if(cc%i==0)
{
p[++top]=i;
w[top]=1;
while(cc%i==0)
{
cc/=i;
w[top]*=i;
}
}
}
if(cc>1)p[++top]=w[top]=cc;
rep(1,top,i)
{
M=w[i];MM=p[i];
prepare();
rep(0,n-1,j)ans[i][j+1]=solve(n-1,j);
}
ll sum=0;
rep(1,n,i)
{
ll cnt=0;
rep(1,top,j)
{
M=mod/w[j];
ll ww=inv(M,w[j]);
cnt=(cnt+ww*M%mod*ans[j][i])%mod;
//cout<<ans[j][i]<<endl;
}
//cout<<cnt<<endl;
sum=(sum+cnt*a[i])%mod;
}
putl(sum);return 0;
}
复杂度为分解的(质因数个数cdot nlog^2.)
由于全部开ll 了所以常数大的一匹 喜提比暴力分还低的40分.
(我们直接暴力都比这个分数高。
很容易考虑到另外一种思路 逐项计算C(n,m) 我们已知 C(n,m-1) 推出C(n,m)即可。
当然很好推 (C(n,m)=C(n,m-1)cdot frac{n-m+1}{m})
发现 m和mod 可能不互质 这就很不爽.
考虑mod是一个质数的时候 利用质因数分解约分法 就是说把分子分母同时对于mod来分解 继续约分 然后约过分之后发现分母和mod互质 求逆元即可。
不是质数的时候 质因数分解一下 采用刚才的套路 对所有分解出来的质数进行类似于这种的约分 最后是互质的求逆元即可。
这里有一个trick 求逆元的时候 由于不一定满足费马小定理 所以需要exgcd 但是也可以求出来 mod的欧拉函数 采用欧拉定理来求逆元。
复杂度(质因子个数cdot nlogn)
onst int maxn=11;
int n,mod,top;
int w[maxn],p[maxn],c[maxn];
inline int ksm(ll b,int p)
{
ll cnt=1;
while(p)
{
if(p&1)cnt=cnt*b%mod;
b=b*b%mod;p=p>>1;
}
return cnt;
}
inline int insert(int x,int y)
{
rep(1,top,i)while(x%p[i]==0)x/=p[i],c[i]+=y;
return x;
}
signed main()
{
freopen("1.in","r",stdin);
//freopen("magic.out","w",stdout);
get(n);get(mod);
int s=mod,phi=mod;
for(int i=2;i*i<=s;++i)
{
if(s%i==0)
{
p[++top]=i;
phi=phi/i*(i-1);
while(s%i==0)s/=i,++w[top];
}
}
if(s>1)p[++top]=s,w[top]=1,phi=phi/s*(s-1);
ll ans=1,sum=0;//ans表示组合数
rep(1,n,i)
{
ll ww=ans;
rep(1,top,j)ww=ww*ksm(p[j],c[j])%mod;
sum=(sum+ww*read())%mod;
if(i!=n)ans=ans*insert(n-i,1)%mod*ksm(insert(i,-1),phi-1)%mod;
}
put(sum);
return 0;
}
题解上给的则是逐项计算 然后对于每个质因子采用上述约分法 但是对于某个质因子单独算出答案 最后采用CRT合并。
复杂度和上面那个复杂度差不多不过要麻烦一点。
还是一个没脑子选手。