Atcoder 236

AtCoder Beginner Contest 236

\(Ex.Distinct Multiples\)

题意

给定\(N\)个数\(D=(D_1,D_2,...,D_N)\)和一个正整数\(M\)，问有多少种方法构造一个长度为\(N\)的序列\(A=(A_1,A_2,...,A_N)\)，使得\(A\)满足以下条件：

\(1\le A_i\le M\)
\(A_i\neq A_j\) \((i\neq j)\)
\(D_i|A_i\)

\(2\le N\le 16\) \(1\le M\le 10^{18}\) \(1\le D_i\le M\)

Sol

组合数学

由于\(N\)很小，所以可以考虑用状态压缩。

以这\(N\)个数有几个数相同划分集合，用二进制来表示，那么根据容斥原理，假设当前的集合是\(S\)，假设\(S\)在二进制下第\(i_1,i_2,...,i_m\)位是\(1\)，那么容斥系数就是\((-1)^{m-1}\times(m-1)!\times \lfloor \frac{M}{LCM(D_{i_1},D_{i_2},...,D_{i_m})}\rfloor\)

#include 
#define ll long long
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;

template  void rd (T &x)
{
    x=0;int f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
    x*=f;
}
template  void chkMax(T &x, T y) { if (y > x) x = y; }
template  void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=1<<17;
ll fac[N];
int cal(int s)
{
  int cnt=0;
  for(int i=0;i<=17;i++)
    if((s>>i)&1) cnt++;
  return cnt; 
}
int lowbit(int s){return s&-s;}
int main()
{
    fac[0]=1;
    int n;
    ll M;
    rd(n),rd(M);
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    vectorD(n),xs(n+1);
    for(int i=0;ig(1<>i)&1)
            {
               ll o=__gcd(v,D[i]);
               if(v*1.0*D[i]/o>2E18)
               {
                  v=M+1;
                  break;
               }
               v=v*D[i]/o;//求lcm
            }
        g[s]=(M/v%mod*xs[cal(s)])%mod;
        if(g[s]<0) g[s]=(g[s]+mod)%mod;
        
    } 
    vectordp(1<


\(G.Good Vertices\)
题意
有一个有\(N\)个点的有向图，现在总共有\(T\)秒，每\(1\)秒会加入一条有向边。定义一个点\(v\)是漂亮的：从点\(1\)可以到点\(v\)并且经过且只经过\(L\)条边。
现在每一个点\(v\)，如果它不是漂亮的点，输出\(-1\)，否则输出这个点\(v\)最早被认为是漂亮的点的时间。
\(2\le N\le 100\)           \(1\le T\le N^2\)          \(1\le N\le 10^9\)               不会出现重边
Sol
把加入的时间当做边权建立一个完全有向图，对于没有加入的边，边权定义为\(inf\)
定义\(dp[i][v]\)表示从点\(1\)到点\(v\)经过且只经过\(i\)条边的最小边权
初始状态：对于点\(2,3,...,N\)，\(dp[0][i]=inf\)                                      \(dp[0][1]=0\)
转移就是：\(dp[i][v]=min_{1\le u\le N}max\{dp[i-1][u],w(u,v)\}\)
为什么这里去\(max\)是因为满足条件的边如果后加那么这个时间就应该是后加的时间，比如从点\(1\)到\(u\)走\(i-1\)步，第\(i\)步走\(w(u,v)\)，如果前\(i-1\)步中存在大于第\(i\)步的时间，那么这条路径的最早时间应该是这条路径上的最大权值，但我们要求的是最早时间，所以对所有满足条件的路径取\(min\)
继续优化：
将取\(min\)看做加法，将取\(max\)看做乘法
那么\(dp[i][v]=\sum_{u=1}^N(dp[i-1][u]\times w(u,v))\)
写成矩阵的形式
#include 
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;

template  void rd (T &x)
{
    x=0;int f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
    x*=f;
}
template  void chkMax(T &x, T y) { if (y > x) x = y; }
template  void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=105;
int n,T,L;
struct matrix
{
    int a[N][N];
    matrix(){memset(a,inf,sizeof a);}
    matrix operator * (const matrix &t)
    {
        matrix C;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    C.a[i][j]=min(C.a[i][j],max(a[i][k],t.a[k][j]));
        return C;
    }
};
int main()
{
    rd(n),rd(T),rd(L);
    matrix A,B;
    for(int i=1;i<=T;i++){
        int u,v;
        rd(u),rd(v);
        B.a[u][v]=i;
    }  
    A.a[1][1]=0;
    while(L)
    {
        if(L&1) A=A*B;
        B=B*B;
        L>>=1;
    }
    for(int i=1;i<=n;i++)
        if(A.a[1][i]==inf) cout<<-1<<' ';
        else cout<

Atcoder 236

AtCoder Beginner Contest 236

相关

标签