Submission #41444618

---

Source Code Expand

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int> 
using namespace std;
 
template<typename T=int> inline T read()
{
	T s=0,w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*w;
}
template<typename T=long long> inline void write(T x,char ch)
{
	if(x<0) x=-x,putchar('-');
	static char stk[25]; int top=0;
	do {stk[top++]=x%10+'0',x/=10;} while(x);
	while(top) putchar(stk[--top]);
	putchar(ch);
	return;
}
 
namespace MyTool
{
	static const int Mod=998244353;
	template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
	template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
	template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
	inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
	inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
	inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
	inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
	inline int  Cadd(int a,int b)  {return a+b>=Mod?a+b-Mod:a+b;}
	inline int  Cdel(int a,int b)  {return a-b<0?a-b+Mod:a-b;}
	inline int  Cmul(int a,int b)  {return a*b%Mod;}
	inline int  Cmod(int a)  {return (a%Mod+Mod)%Mod;}
	inline int  gcd(int a,int b)   {return b?gcd(b,a%b):a;}
	inline int  qpow(int a,int b)  {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
	inline int  qmul(int a,int b)  {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
	template<typename T> inline T power(T x)    {return x*x;}
}
using namespace MyTool;
 
inline void file()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	return;
}
 
bool Mbe;
 
namespace LgxTpre
{
	static const int MAX=210;
	static const int inf=2147483647;
	static const int INF=4557430888798830399;
	static const int mod=1e9+7;
	static const int bas=131;
	
	int n,ans,a[MAX];
	int all=1,num12=1,pw=1;
	int flag1,flag2,flag3;
	int mix1=INF,mix2=-INF,top;
	int f[MAX][1<<17],g[1<<17];
	
	bool dfs(int S)
	{
		if(!S) return 1;
		if(g[S]!=-1) return g[S];
		int mix=(64-__builtin_clzll(S))*12;
		for(int i=1;i<=mix;++i) 
		{
			set<int> s;
			for(int j=0;j<top;++j) if((S>>j&1)&&(12*(j+1)%i)) s.insert(12*(j+1)%i);
			if(((int)s.size()==1&&*s.begin()<=2)||((int)s.size()==2&&*s.begin()==4&&*s.rbegin()==8)) return g[S]=1,1;
			int T=0,flag=1;
			for(auto it:s)
			{
				if(it%12) {flag=0; break;}
				T|=(1<<((it/12)-1));
			}
			if(flag&&!dfs(T)) return g[S]=1,1;
		}
		return g[S]=0,0;
	}
	
	inline void mian()
	{
		n=read();
		for(int i=1;i<=n;++i)
		{
			a[i]=read(),cmin(mix1,a[i]),cmax(mix2,a[i]),cmax(top,a[i]/12);
			Mmul(all,a[i]),Mmul(num12,a[i]/12);
			if(a[i]<2) flag1=1;
			if(a[i]<4) flag2=1;
			else if(a[i]<8) flag3=1;
			else Mmul(pw,2ll);
		}
		ans=Cdel(all,Cadd(num12,1ll));
		if(!flag1) Mdel(ans,1ll);
		if(!flag2) Mdel(ans,Cdel(pw,!flag3+1));
		if(mix1<12) return write(ans,'\n');
		f[0][0]=1,memset(g,-1,sizeof g);
		for(int i=1;i<=n;++i) for(int S=0;S<(1<<top);++S) 
			if(f[i-1][S]) for(int now=0,T=S|(1<<now);(now+1)*12<=a[i];++now,T=S|(1<<now))
				Madd(f[i][T],f[i-1][S]);
		for(int S=0;S<(1<<top);++S) if(dfs(S)) Madd(ans,f[n][S]);
		write(ans,'\n');
		return;
	}
}
 
bool Med;
 
signed main()
{
//	file();
	fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
	LgxTpre::mian();
	cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
	return (0-0);
}

Submission Info

Judge Result