HGOI 20190821 慈溪一中互测

╰+哭是因爲堅強的太久メ 2023-06-05 11:26 19阅读 0赞

**Problem A**

> 给出一个$n$个点$m$条边的仙人掌图（每条边最多处于一个简单环中）。
> 
> 使用$c$种颜色对这张图中的顶点染色，使得每一条无向边连接的两个点颜色不同。
> 
> 求染色的方案数，$mod \\ 998244353$的值。
> 
> 对于$100\\%$的数据满足，$ 1 \\leq n,m \\leq 10^6$

Solution :

对于一棵树的答案非常简单就是$c \\times (c-1) ^ \{n-1\}$

对于一个大环，我们不妨计算这个环上的方案数。

设$f(n)$表示含有$n$个点的环上使用$c$种颜色染色的方案数，

非常显然，$f(1) = c$ , $f(2) = c(c-1)$.

若$c \\geq 3$ 那么考虑对于所有节点不能和前一个刚被染色的节点重复染色，方案数就是$c \\times (c-1)^\{n-1\}$

然后考虑，最后一个点和第一个点的颜色不能重复，若重复，我们可以将其看做一个点，那么就变成了一个子问题。

最终，$f(n) = c \\times (c-1)^\{n-1\} - f(n-1)$

对于仙人掌图我们考虑v-DCC缩点（即找点双联通分量）

对于一个点，可能在多个简单环里。

那么对于这个点，只要被一个环计算过，那么在计算剩余环的时候应当认为这个点的颜色既定。

所以，若多于一个点在$k$个简单环里，我们只需要将总方案数直接除以$c^\{k-1\}$即可，这是由于该点在其他$k-1$个环中被认为可以被染$c$种颜色，然而事实上，这个点的颜色在第一个环包含它的时候已经被计算。

所以，本题只需要进行一遍tarjan的v-DCC缩点即可。

复杂度$O(n)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=1e6+10,mo=998244353;
    int dfn[N],low[N],n,m,tot,head[N],cnt,blo[N],f[N],c;
    vector<int>dcc[N];
    stack<int>s;
    struct rec{
        int pre,to;
    }a[N<<2];
    void adde(int u,int v) {
        a[++tot].pre=head[u];
        a[tot].to=v;
        head[u]=tot;
    }
    int Pow(int x,int n) {
        int ans = 1;
        while (n) {
            if (n&1) ans=ans*x%mo;
            x=x*x%mo;
            n>>=1;
        }
        return ans%mo;
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++dfn[0]; s.push(u);
        for (int i=head[u];i;i=a[i].pre){
            int v=a[i].to; 
            if (!dfn[v]) {
                tarjan(v); low[u]=min(low[u],low[v]);
                if (low[v]>=dfn[u]) {
                    int z; ++cnt;
                    do {
                        z = s.top(); s.pop();
                        dcc[cnt].push_back(z);
                        blo[z]++;
                    }while (v!=z);
                    dcc[cnt].push_back(u);
                    blo[u]++;
                }
            } else low[u] = min(low[u],dfn[v]);
        }
    }
     main()
    {
        scanf("%lld%lld%lld",&n,&m,&c);
        for (int i=1;i<=m;i++) {
            int u,v; scanf("%lld%lld",&u,&v);
            adde(u,v); adde(v,u);
        }
        f[1] = c; f[2] = c*(c-1) % mo;
        for (int i=3;i<=n;i++) 
            f[i]=((c*Pow(c-1,i-1)%mo-f[i-1])%mo+mo)%mo;
        tarjan(1);
        int ans = 1,ret = 0;
        for (int i=1;i<=n;i++) ret+=blo[i]-1;
        for (int i=1;i<=cnt;i++)
            ans = ans*f[dcc[i].size()]%mo;
        int ni = Pow(c,mo-2);   
        ans = ans * Pow(ni,ret) % mo;
        printf("%lld\n",ans);
        return 0;
    }

A.cpp

**Problem B**

> 有一个集合S，初始时为空.给定$n,k$
> 
> 每一次操作，你可以选择1到n中的任意一个不在S中的元素i，并将其加入S，此时如果i-2也在S中，则将i-2从S中删除，
> 
> 如果i+k也在S中，则将i+k从S中删除。该操作可以进行任意多次。郝仁想知道总共有多少种不同的S，对998244353取模  
> 
> 
> 对于$100\\%$的数据$n \\leq 300$

Solution :

首先将集合转化为一个有向图，对于每一个$i$若存在$i-2$和$i+k$，则从$i$连出一条边。

这样本题就转化为一个图上的计数题。

*  若$k$为偶数。

显然序号为奇数和序号为偶数互不干扰，我们可以将奇数序号和偶数序号的分别进行考虑。

问题便转化为有$n$个数里面选择若干个数，最多可以连续选择$m$个数字，方案数。

最后将偶数的方案总数乘以奇数的方案总数即可。

于是我们定义$f\_\{i,j\}$表示前$i$个数字，当前已经连续选择$j$个数字，方案总数。

转移可以采用刷表法：$f\_\{i+1,0\}+=f\_\{i,j\} , f\_\{i+1,j+1\}+=f\_\{i,j\}$

复杂度是$O(nm)$的。

*  若$k$为奇数。

奇数序号和偶数序号相关，我们可以将$1 - n$的序号从小到大从上到下，奇数在左边，偶数在右边。

$i$和$i+k$对齐，这样构成的矩阵，高是$\\left \\lfloor \\frac\{n+1\}\{2\} \\right \\rfloor+ \\left \\lfloor \\frac\{k\}\{2\} \\right \\rfloor$

其中，右侧偶数非空的区间是$\[1,\\left \\lfloor \\frac\{n\}\{2\} \\right \\rfloor\]$

左侧奇数的非空区间是$\[\\left \\lfloor \\frac\{k\}\{2\} \\right \\rfloor , \\left \\lfloor \\frac\{n+1\}\{2\} \\right \\rfloor+ \\left \\lfloor \\frac\{k\}\{2\} \\right \\rfloor\]$

上述结论是基本性质，归纳可证。

考虑一个dp，设$f\[i\]\[j\]\[k\]$表示当前已经考虑到第$i$层了（从上到下，层数从$1$ 到 $\\left \\lfloor \\frac\{n+1\}\{2\} \\right \\rfloor+ \\left \\lfloor \\frac\{k\}\{2\} \\right \\rfloor$）, 在右侧偶数已经连续选择了$j$个元素（为0则为空），在左侧奇数**最多**连续选择了$k$个元素，且必须包含一个拐弯（我们认为从偶数列跳到奇数列为一个"拐弯"）

我们考虑第$i$层，左选/不选，右选/不选的情况，就可以得到四个DP方程。

即

*   *   *  (左右都不选择，无限制) : f\[i\+1\]\[0\]\[0\]=f\[i\]\[j\]\[k\]

*   *   *  (左选右不选择，左边的元素存在，即$i \\in \[\\left \\lfloor \\frac\{k\}\{2\} \\right \\rfloor , \\left \\lfloor \\frac\{n+1\}\{2\} \\right \\rfloor+ \\left \\lfloor \\frac\{k\}\{2\} \\right \\rfloor\]$)

$ f\[i+1\]\[0\]\[k?k+1:0\]+=f\[i\]\[j\]\[k\]$ , 若原来没有或者没有拐弯，那么现在也不会有。

*   *   *  (左不选右选，右边的元素存在，即$i \\in \[1,\\left \\lfloor \\frac\{n\}\{2\} \\right \\rfloor )$)

$f\[i+1\]\[j+1\]\[0\]+=f\[i\]\[j\]\[w\]$

*   *   *  (既选择左，又选择右侧元素，左右元素同时存在，上述两个集合的交集)

$f\[i+1\]\[j+1\]\[max(w+1,j+2)\]+=f\[i\]\[j\]\[w\]$ ， 左侧的状态有两条路来走，我们取较大的一条。

上述DP细节较多，可以采用刷表实现，复杂度会是$O(n^3)$.

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=305,mo=998244353;
    int n,k;
    namespace Subtask1 {
        int f[N][N][N];
        void main() {
            f[0][0][0] = 1;
            for (int i=0;i<(n+1)/2+k/2;i++)
             for (int j=0;j<=n;j++)
              for (int w = 0 ; w <= k+1 ; w++) {
                (f[i+1][0][0]+=f[i][j][w])%=mo;
                if (i>=(k/2)) (f[i+1][0][w?w+1:0]+=f[i][j][w])%=mo;
                if (i<n/2) (f[i+1][j+1][0]+=f[i][j][w])%=mo;
                if (i>=(k/2) && i<(n/2)) (f[i+1][j+1][max(w+1,j+2)]+=f[i][j][w])%=mo;
              }
            int ans = 0;
            for (int j=0;j<=n;j++)
             for (int w=0;w<=k+1;w++)
              (ans+=f[(n+1)/2+k/2][j][w])%=mo;
            cout<<ans<<'\n';
            exit(0);
        }
    }
    namespace Subtask2 {
        int f[N][N];
        int g(int n,int m) {
            memset(f,0,sizeof(f)); f[0][0] = 1;
            for (int i=0;i<=n;i++)
            for (int j=0;j<=m;j++) {
                f[i+1][0]=(f[i+1][0]+f[i][j])%mo;
                if (j+1<=m) f[i+1][j+1]=(f[i+1][j+1]+f[i][j])%mo;
            }
            int ret=0;
            for (int i=0;i<=m;i++) ret=(ret+f[n][i])%mo;
            return ret % mo;
        }
        void main() {
            int ans = 1ll * g((int)ceil((double)n/2.0),k/2) * g(n/2,k/2) % mo;
            cout<<ans<<'\n';
            exit(0);
        }
    }
    signed main() {
        cin>>n>>k;
        if (k&1) Subtask1::main();
        else Subtask2::main();
        return 0;
    }

B.cpp

**Problem C**

> 　　维护序列$a\_i$支持$q$次查询操作，形如$l,r,d$表示在区间$\[l,r\]$中是$d$倍数的数的个数。
> 
> 　　对于$100\\%$的数据满足$n,q,a\_i \\leq 10^5$

Solution : 直接暴力分块，每一块中维护这个块内约数为$i , i \\in \[1,10^5\]$的数的个数，方便$O(1)$查询。

对于块外元素，直接暴力，对于块内元素，直接跑块即可。

时空复杂度都是$O(n \\sqrt\{n\})$　　。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# pragma GCC optimize(3)
    # include <bits/stdc++.h>
    # define Rint register int
    using namespace std;
    const int N=1e5+1;
    struct rec{
        int l,r,cnt[N];
    }tr[318];
    int n,m,a[N],blong[N],block,num;
    inline int read()
    {
        int X=0; char c=0;
        while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return X;
    }
    void write(Rint x) {
        if (x>9) write(x/10);
        putchar('0'+x%10);
    }
    inline void writeln(Rint x) {
        write(x); putchar('\n');
    }
    int query(int l,int r,int d)
    {
        int ret = 0;
        if (blong[l] == blong[r]) {
            for (Rint i=l;i<=r;i++)
             if (a[i]%d == 0) ret++;
            return ret; 
        }
        for (Rint i=l;i<=tr[blong[l]].r;i++) 
         if (a[i]%d == 0) ret++;
        for (Rint i=tr[blong[r]].l;i<=r;i++) 
         if (a[i]%d == 0) ret++;
        for (Rint i = blong[l]+1 ; i<=blong[r]-1; i++) 
         if (d<=n) ret+=tr[i].cnt[d];
        return ret;  
    }
    int main()
    {
        n = read(); m =read();
        for (Rint i=1;i<=n;i++) a[i]=read();
        block=sqrt(n); 
        num=n/block; if (n%block) num++;
        for (Rint i=1;i<=num;i++) {
            tr[i].l=(i-1)*block+1,
            tr[i].r=i*block;
        }
        tr[num].r=n;
        for (Rint i=1;i<=n;i++) {
            blong[i]=(i-1)/block+1;
            for (Rint j=1;j<=sqrt(a[i]);j++) {
                if (a[i]%j!=0) continue; 
                tr[blong[i]].cnt[j]++; 
                if (j*j!=a[i]) tr[blong[i]].cnt[a[i]/j]++;
            } 
        }
        int l,r,d;
        while (m--) {
            l = read(),r =read(),d=read(); 
            query(l,r,d);
            writeln(query(l,r,d));
        }
        return 0;
    }

C.cpp

转载于:https://www.cnblogs.com/ljc20020730/p/11391007.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c1d17b2d75a24cf5a644665a8b80f328.png