CF1043F Make It One 容斥原理+dp

Code: 

#include <cstdio> 
#include <algorithm>   
#define ll long long  
#define N 300002 
#define mod 998244353 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;          
ll fac[N],inv[N];  
int arr[N],cnt[N],f[12][300001];      
ll qpow(ll base,ll k) 
{
	ll tmp=1; 
	for(;k;base=base*base%mod,k>>=1) tmp=tmp*base%mod; 
	return tmp;    
} 
ll C(int n,int m) 
{ 
	if(n<m) return 0; 
	return fac[n]*inv[m]%mod*inv[n-m]%mod;   
}
int main() 
{ 
	int i,j,n,M=0;
	// setIO("input");       
	scanf("%d",&n); 
	for(i=1;i<=n;++i) 
	{ 
		scanf("%d",&arr[i]), cnt[arr[i]]++, f[1][arr[i]]++;   
		M=max(M,arr[i]); 
		if(arr[i]==1) 
		{
			printf("1\n"); 
			return 0; 
		}
	} 
	fac[0]=1;    
	for(i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod;           
	inv[N-1]=qpow(fac[N-1],mod-2); 
	for(i=N-1;i>=1;--i) inv[i-1]=i*inv[i]%mod;        
	for(i=1;i<=M;++i) 
		for(j=i+i;j<=M;j+=i) cnt[i]+=cnt[j];                      
	for(i=2;i<=11;++i) 
	{
		for(j=M;j>=1;--j) 
		{
			f[i][j]=C(cnt[j], i);
			for(int k=j+j;k<=M;k+=j) f[i][j]=(f[i][j]-f[i][k]+mod)%mod; 
		}
	    if(f[i][1]>0)                       
	    {
	    	printf("%d\n",i); 
	    	return 0; 
	    }
	}
	printf("-1\n");   
	return 0; 
}

  

上一篇:数论


下一篇:Codeforces Round #736 (Div. 2) 部分题题解