Submission #34841215

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N=16;
mint fac[20]={1};
mint f[1<<N]={1};
ll a[20];
ll lcm[1<<N] = {1}; // 如果过大 用 m+1表示
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}
int c[1<<N] = {0};
int main(){
  int n = read();
  ll m = read();
  rep(i,0,n) a[i]=read();
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  rep(i,1,1<<n) c[i]=c[i&(i-1)]+1;
  rep(mask,1,1<<n){
    int p=__builtin_ctz(mask); // 最低位1的二的幂次
    int b=1<<p;
    ll u=lcm[mask^b];
    ll v=a[p];
    ll w=gcd(u,v);
    lcm[mask] = (u/w<=m/v)? u/w*v : (m+1); // 注意overflow 这里直接设置m+1 来避免overflow 而让结果 = 0
    // 非空子集遍历 包含最低位 dp[mask] = dp[mask0 not contain lowbit] * (g*h)(mask\mask0)
    for(int j=mask;j;j=(j-1)&mask) if(j&b) f[mask]+=f[mask^j]*fac[c[j]-1]*(m/lcm[j])*(c[j]&1?1:-1);
  }
  printf("%d\n",(f[(1<<n)-1]).val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:7:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    7 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result