为什么这玩意在本地跑了20s+,交上去就过了啊……

理论复杂度 $O(3^mm^2\log n)$，也跑不过去啊……

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

ll a[55],dp[61][1<<11][55],dp2[61][1<<11][55],to[1<<10+1][1<<10+1],C[55][55],n,m;
const ll mod=998244353;

ll qkp(ll a,ll k){
	ll ans=1;
	while(k){
		if (k&1)ans*=a,ans%=mod;
		a*=a,a%=mod;
		k>>=1;
	}
	return ans;
}

ll C2(ll n,ll m){
	if (n<m||n<0||m<0)return 0;
	ll ans=1;
	for (ll i=n-m+1;i<=n;i++){
		ans*=i%mod;ans%=mod;
		ans*=qkp(n-i+1,mod-2);ans%=mod;
	}
	return ans;
}

int main() {
	C[0][0]=1;
	for (ll i=1;i<=10;i++){
		C[i][0]=1;
		for (ll j=1;j<=10;j++){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	cin>> n>> m;
	for (ll i=1; i<=m; i++) {
		cin >> a[i];
	}
	dp[60][(1<<m)-1][0]=1;
	for (ll i=60; i>=1; i--) {
		for (ll j=0; j<=(1<<m)-1; j++) {
			ll tot=m;
			for (ll k=0;k<m;k++)if (j>>k&1)tot--;
			for (ll k=j;; k=(k-1)&j) {
				ll newlim=0,fl=1;
				for (ll z=1; z<=m; z++) {
					if (k>>(z-1)&1) { // 这一位填1
						if (!(a[z]>>i&1)&&(j>>(z-1)&1)) { // 这一位上是0并且这一位有限制，所以不合法
							fl=0;
							break;
						} else {
							newlim|=(1<<(z-1))*(j>>(z-1)&1);// 这一位上是1，如果之前有限制那就有限制
						}
					} else { // 这一位填0
						if (!(a[z]>>i&1)) {
							newlim|=(1<<(z-1))*(j>>(z-1)&1); // 这一位上是0，那么之前有限制那就有限制
						}
						// 这一位上是1，一定没限制
					}
				}
				if (fl)
					to[j][k]=newlim;
				else
					to[j][k]=-1;
				if (to[j][k]==-1)continue;
				ll v=__builtin_popcount(k);
				for (ll v2=0; v2<=tot; v2++) {
					if((v+v2)&1)continue; 
					for (ll cnt=v+v2; cnt<=2*m+1; cnt++) {

						dp[i-1][to[j][k]][min(2*m+1,2*(cnt-v-v2)+(n>>(i-1)&1))]+=dp[i][j][cnt]*C[tot][v2]%mod;
						dp[i-1][to[j][k]][min(2*m+1,2*(cnt-v-v2)+(n>>(i-1)&1))]%=mod;
					}
					
				}
				if (k==0)break;
			}
		}
	}
	ll ans=0;
	for (ll i=0; i<=(1<<m)-1; i++) {
		for (ll k=0; k<=(1<<m)-1; k++) {
			ll v=__builtin_popcount(k);
			if (v%2)continue;
			ll newlim=0,fl=1;
			for (ll z=1; z<=m; z++) {
				if (k>>(z-1)&1) { // 这一位填1
					if (!(a[z]&1)&&(i>>(z-1)&1)) { // 这一位上是0并且这一位有限制，所以不合法
						fl=0;
						break;
					} else {
						newlim|=(1<<(z-1))*(i>>(z-1)&1);// 这一位上是1，如果之前有限制那就有限制
					}
				} else { // 这一位填0
					if (!(a[z]&1)) {
						newlim|=(1<<(z-1))*(i>>(z-1)&1); // 这一位上是0，那么之前有限制那就有限制
					}
					// 这一位上是1，一定没限制
				}
			}
			if (fl)
				to[i][k]=newlim;
			else
				to[i][k]=-1;
			if (to[i][k]==-1)continue;
			ans+=dp[0][i][v];
			ans%=mod;
		}
	}
	// 计算总方案数
	ll ans2=0;
	for (ll i=0;i<=(1<<m)-1;i++){
		ll tot=n;
		for (ll j=1;j<=m;j++){
			if (i>>(j-1)&1)tot-=a[j]+1;
		}
		if (__builtin_popcount(i)%2)ans2-=C2(tot+m-1,m-1);
		else ans2+=C2(tot+m-1,m-1);
		ans2=(ans2+mod)%mod;
	}
	cout<< (ans2-ans+mod)%mod;
	return 0;
}