AtCoder Beginner Contest 304

F - Shift Table

题意

给定一个长度为 $n$ 的字符串 $s$ 代表 $A$ 的工作模式：第 $i$ 个字符为 # 代表 $A$ 在第 $i$ 天工作，为 . 代表 $A$ 在第 $i$ 天不工作。现构造一个长度为 $m$ 的字符串 $t'$（$m$ 是 $n$ 的因子且 $m\neq n$） ，将其拷贝 $\dfrac{n}{m}$ 份得到字符串 $t$，代表 $B$ 的工作模式。 要求在这 $n$ 天中，每一天都至少有一人工作。求不同的字符串 $t$ 的数量。

题解

记 $f(n)$为长度为 $n$ 的字符串 $t'$ 能生成的不同字符串 $t$ 的数量。注意到，长度是 $n$ 的因子的字符串 $t''$ 生成的字符串可能和 $t'$ 生成的相同，例如：$t'$ 为 ## 而 $t''$ 为 #。所以，我们再定义 $g(n)$ 为长度为 $n$ 的字符串 $t'$ 能生成的，且不能由更短的字符串生成的不同字符串 $t$ 的数量。

最终我们要求的式子为

$$\sum_{i\mid n,i\neq n}g(i)$$

直接求 $g$ 不太好求，但是 $f$ 容易求得。所以考虑 $f$ 和 $g$ 的关系

$$f(n)=\sum_{d|n}g(d)$$

这是莫比乌斯反演的经典形式，很容易得到

$$g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$$

接下来就是推式子

$$\begin{aligned} \sum_{i\mid n,i\neq n}g(i) &=\sum_{i\mid n,i\neq n}\sum_{d\mid n}\mu(d)f(\frac{n}{d})\\ &=\sum_{d\mid n,d\neq n}f(d)\sum_{k\mid n,k\neq \frac{n}{d}}\mu(d)\\ &=\sum_{d\mid n,d\neq n}f(d)(\epsilon(\frac{n}{d})-\mu(\frac{n}{d}))\\ &=\sum_{d\mid n,d\neq n}-\mu(\frac{n}{d})f(d) \end{aligned}$$

然后这个题目就做完了qwq。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5;
const int p=998244353;
int n,cnt,f[maxn+5],vis[maxn+5],pri[maxn+5],mu[maxn+5],tag[maxn+5];
ll P2[maxn+5];
string s;
void init()
{
    mu[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<=maxn;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=-mu[i];
        }
    }
    P2[0]=1;
    for(int i=1;i<=maxn;i++) P2[i]=P2[i-1]*2%p;
}
void solve(int m)
{
    for(int i=1;i<=m;i++) tag[i]=0;
    for(int i=0;i<n;i++) 
        if(s[i]=='.') tag[i%m+1]=1;
    int cnt=0;
    for(int i=1;i<=m;i++)
        if(!tag[i]) cnt++;
    f[m]=P2[cnt]; 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    cin>>n>>s;
    ll ans=0;
    for(int i=1;i<n;i++)
    {
        if(n%i) continue;
        solve(i);
        ans=(ans-mu[n/i]*f[i]%p+p)%p;
    }
    cout<<ans<<'\n';
    return 0;
}

H - Constrained Topological Sort

题意

给定一张有向图，含有一些边 $(s_i,t_i)$。同时，给出一些限制 $(l_i,r_i)$。要求构造一个排列 $p$，满足以下条件：

• $p_{s_i}<p_{t_i}$
• $l_i\leq p_i\leq r_i$

题解

很显然这张图一定是DAG，否则无法满足条件1。

由于存在拓扑关系，每个限制 $(l_i,r_i)$ 事实上也会限制每个点的前驱。具体地，对于边 $(s,t)$，有 $p_s\leq r_s$ 且 $p_s\leq p_t-1\leq r_t$。即 $p_s\leq \min(r_s,r_t-1)$。所以，在反图上跑一遍拓扑序，更新一下每个点的上界，保证对每条边 $(s,t)$，有 $r_s<r_t$。

接下来考虑构造这个排列，从 $1$ 到 $n$ 依次将每个数分配，在分配 $i$ 时，候选点 $v$ 需要满足两个条件：

• $l_v\leq i$
• $v$ 的所有前驱都已被分配了数

在所有候选点中，选择 $r$ 最小的，将 $i$ 分配给它。

最后还需要再检查一遍是否满足题目给出的两个限制。

（正确性的证明可以参考官方题解）

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int p[maxn],in[maxn],in1[maxn];
vector<int> a[maxn];
vector<int> g[maxn],g1[maxn];
struct node
{
    int id,l,r;
    bool operator < (const node x) const {return r>x.r;}
}nodes[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g1[v].push_back(u);
        in[v]++,in1[u]++;
    }
    for(int i=1;i<=n;i++)
    {
        int l,r;cin>>l>>r;
        nodes[i]={i,l,r};
        a[l].push_back(i);
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!in1[i]) q.push(i);
    int cnt=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        cnt++;
        for(auto v:g1[u])
        {
            nodes[v].r=min(nodes[v].r,nodes[u].r-1);
            in1[v]--;
            if(!in1[v]) q.push(v);
        }
    }
    if(cnt!=n) cout<<"No"<<'\n';
    else
    {
        priority_queue<node> pq;
        for(int i=1;i<=n;i++)
        {
            for(auto j:a[i]) 
                if(!in[j]) pq.push(nodes[j]);
            if(pq.empty()) break;
            int u=pq.top().id;pq.pop();
            p[u]=i;
            for(auto v:g[u])
            {
                in[v]--;
                if(!in[v]&&nodes[v].l<=i) pq.push(nodes[v]);
            }
        }
        bool ok=1;
        for(int i=1;i<=n;i++)
        {
            if(p[i]<nodes[i].l||p[i]>nodes[i].r) ok=0;
            for(auto j:g[i])
                if(p[j]<p[i]) ok=0;
        }
        if(!ok) cout<<"No"<<'\n';
        else
        {
            cout<<"Yes"<<'\n';
            for(int i=1;i<=n;i++) cout<<p[i]<<" \n"[i==n];
        }
    }
    return 0;
}