abc317f
abc317f
一看就是数位dp，但之前还想错了，今天课上突然想到
之前想的是怎样构造保证能够整除
但实际上将余数也设计到状态中就行
其他就是基本的数位dp
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++) //
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define ff(i,a,b) for ((i)=(a);(i)<=(b);(i)++)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
ll f[100][8][11][11][11][8];
ll b[100],k,n,tot,d[100],r[10],a[10],rr[10],ss,ans;
void add(ll &x, ll y){
x=(x+y)%mo;
}
bool F(ll x,ll y){
if (x && y) return 1;
if (!x && !y) return 1;
return 0;
}
void solve(){
f[tot+1][7][0][0][0][0]=1; //
fd(i,tot,0){
fo(s,0,7) ff(r[0],0,a[0]-1) ff(r[1],0,a[1]-1) ff(r[2],0,a[2]-1) {
fo(sw,0,7) {
if (!f[i+1][s][r[0]][r[1]][r[2]][sw]) continue;
int temp;
bool flag;
fo(t,0,7) {
temp=0;
flag=1;
ss=0;
fo(j,0,2) {
if (t&b[j]) temp^=1;
if ((s&b[j]) && (t&b[j]) && (!d[i])) flag=0;
if ((s&b[j]) && F(t&b[j], d[i])) ss|=b[j];
}
if (temp || !flag) continue;
fo(j,0,2) {
rr[j]=r[j];
if (t&b[j]) rr[j]=(rr[j]+b[i])%a[j];
}
add(f[i][ss][rr[0]][rr[1]][rr[2]][sw|t], f[i+1][s][r[0]][r[1]][r[2]][sw]);
}
}
}
}
fo(s,0,7) {
add(ans, f[0][s][0][0][0][7]);
}
}
int main()
{
// freopen("data.in","r",stdin);
b[0]=1;
fo(i,1,62) b[i]=b[i-1]*2ll;
scanf("%lld",&n);
fo(i,0,2) scanf("%lld",&a[i]);
k=n; tot=0;
while (k){
d[tot++]=k&1;
k/=2;
}
solve();
printf("%lld",ans);
return 0;
}