自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 22:59:29，当前版本为作者最后更新于2024-06-20 23:00:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

勘误 2024.6.22：时间复杂度应为 $O(p^2V+pV\log (pV))$。感谢 @NaCly_Fish。

问题的难点在于如何钦定每个位置不被重复选。否则就是直接看作是多项式，进行卷积即可。

考虑容斥，钦定某些点被选 $1\sim p$ 次。这类所有点不等的容斥系数，钦定某个点出现 $x$ 次时系数为 $(-1)^{x-1}(x-1)!$。可以使用动态规划计算出。

注意到卷积时暴力 $O(p^2V\log V)$ 无法通过。我们需要点值的多项式只有 $O(p)$ 个。于是先把所有初始多项式转化成点值的形式，然后进行 dp 后只在 $p$ 位置 IDFT 回来即可。

总复杂度 $O(p^2V+pV\log(pV))$，可以通过。

#include <bits/stdc++.h>
#define int __int128
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
int read(){
	long long x; cin>>x;
	return x;
}
void print(int x){
	cout<<(long long)x;
}
namespace Conv{
    typedef long long ll;
    const int mod=4179340454199820289,N=1050000,g=3,invg=(mod+1)/3;
    int wk[N+5],ta[N+5],tb[N+5];
    int Power(int x,int y){
    	int r=1;
    	while(y){
    		if(y&1)r=1ll*r*x%mod;
    		x=1ll*x*x%mod,y>>=1;
    	}
    	return r;
    }
    void DFT(int *a,int n){
    	for(int i=n>>1;i;i>>=1){
    		int w=Power(g,(mod-1)/(i<<1));
    		wk[0]=1;
    		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
    		for(int j=0;j<n;j+=(i<<1)){
    			for(int k=0;k<i;k++){
    				int x=a[j+k],y=a[i+j+k],z=x;
    				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
    				z-=y,(z<0&&(z+=mod)),a[i+j+k]=1ll*z*wk[k]%mod;
    			}
    		}
    	}
    }
    void IDFT(int *a,int n){
    	for(int i=1;i<n;i<<=1){
    		int w=Power(invg,(mod-1)/(i<<1));
    		wk[0]=1;
    		for(int j=1;j<i;j++)wk[j]=1ll*wk[j-1]*w%mod;
    		for(int j=0;j<n;j+=(i<<1)){
    			for(int k=0;k<i;k++){
    				int x=a[j+k],y=1ll*a[i+j+k]*wk[k]%mod,z=x;
    				x+=y,(x>=mod&&(x-=mod)),a[j+k]=x;
    				z-=y,(z<0&&(z+=mod)),a[i+j+k]=z;
    			}
    		}
    	}
    	for(int i=0,inv=Power(n,mod-2);i<n;i++)a[i]=1ll*a[i]*inv%mod;
    }
    vector<int> conv(vector<int> A,vector<int> B){
    	int sa=A.size(),sb=B.size();
    	vector<int> ret(sa+sb-1);
    	int len=1;
    	while(len<ret.size())len<<=1;
    	for(int i=0;i<len;i++)ta[i]=tb[i]=0;
    	for(int i=0;i<sa;i++)ta[i]=A[i];
    	for(int i=0;i<sb;i++)tb[i]=B[i];
    	DFT(ta,len),DFT(tb,len);
    	for(int i=0;i<len;i++)ta[i]=1ll*ta[i]*tb[i]%mod;
    	IDFT(ta,len);
    	for(int i=0;i<ret.size();i++)ret[i]=ta[i];
    	while(ret.size()>A.size()) ret.pop_back();
    	return ret;
    }
    vector<int> getdft(vector<int> A,int len){
    	for(int i=0;i<len;i++)ta[i]=0;
    	for(int i=0;i<A.size();i++)ta[i]=A[i];
    	DFT(ta,len);
    	A.resize(len);
    	for(int i=0;i<len;i++) A[i]=ta[i];
    	return A;
	}
    vector<int> getidft(vector<int> A,int len,int alen){
    	for(int i=0;i<len;i++)ta[i]=0;
    	for(int i=0;i<A.size();i++)ta[i]=A[i];
    	IDFT(ta,len);
    	A.resize(alen);
    	for(int i=0;i<alen;i++) A[i]=ta[i];
    	return A;
	}
    vector<int> add(vector<int> A,vector<int> B){
    	if(A.size()!=B.size()) exit(2);
    	for(int i=0;i<B.size();i++) (A[i]+=B[i])%=mod;
    	return A;
	}
    vector<int> mul(vector<int> A,int B){
    	for(int i=0;i<A.size();i++) (A[i]*=B)%=mod;
    	return A;
	}
}
const int mod=4179340454199820289;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return ans;
}
int fac[6],C[6][6];
void solve(){
	int n=read(),m=read();
	int maxv=0; vector<int> vc;
	for(int i=1;i<=n;i++){
		int x=read(); vc.push_back(x);
		maxv=max(maxv,x);
	}
	vector<int> a[6],b[6];
	vector<int> ap[6],bp[6];
	for(int i=0;i<=m;i++){
		while(a[i].size()<maxv*m+1) a[i].emplace_back(0);
		while(b[i].size()<maxv*m+1) b[i].emplace_back(0);
	}
	int f=a[0].size()*2-1;
	int len=1;
	while(len<f) len<<=1;
	for(int i=0;i<=m;i++) while(bp[i].size()<len) bp[i].emplace_back(0);
	for(int i=1;i<=m;i++) for(auto v:vc) a[i][v*i]+=fac[i-1];
	for(int i=1;i<=m;i++) ap[i]=Conv::getdft(a[i],len);
	b[0][0]=1;
	bp[0]=Conv::getdft(b[0],len);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=i;j++){
			for(int l=0;l<len;l++) (bp[i][l]+=bp[i-j][l]*ap[j][l]%mod*C[i-1][j-1])%=mod;
//			b[i]=Conv::add(b[i],Conv::mul(Conv::conv(b[i-j],a[j]),C[i-1][j-1]));
		}
//		bp[i]=Conv::getdft(b[i],len);
	}
	b[m]=Conv::getidft(bp[m],len,a[0].size());
	int inv=1;
	for(int i=1;i<=m;i++) (inv*=i)%=mod;
	inv=qp(inv,mod-2);
	for(int i=0;i<b[m].size();i++){
		if(b[m][i]){
			cout<<(long long)i<<": "<<(long long)(b[m][i]*inv%mod)<<"\n";
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	for(int i=0;i<=5;i++) C[i][0]=1;
	for(int i=1;i<=5;i++) for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	fac[0]=1; for(int i=1;i<=5;i++) fac[i]=fac[i-1]*i;
	for(int i=1;i<=5;i+=2) fac[i]=mod-fac[i];
	int t=read();
	for(int i=1;i<=t;i++){
		cout<<"Case #"<<(long long)i<<":\n";
		solve();
		cout<<"\n"; 
	}
	return 0;
}