AtCoder Beginner Contest 317

https://atcoder.jp/contests/abc317

F - Nim

题意

给定整数 $n,a_1,a_2,a_3$。求解符合以下条件的 $(x_1,x_2,x_3)$ 的个数：

• $1\leq x_i\leq n$
• $x_i$ 是 $a_i$ 的倍数
• $x_1\oplus x_2\oplus x_3=0$

结果对 $998244353$ 取模。

数据范围：$1\leq n\leq 10^{18},1\leq a_i\leq 10$。

题解

数位dp，但是状态设计又和常规的有些不同。感觉还是见得太少了，也不够灵活。

设 $f_{i,j_1,j_2,j_3,r_1,r_2,r_3}$ 表示处理到二进制下从低到高的第 $i$ 位，第 $1,2,3$ 个数的低 $i$ 位是否不超过 $n$ 的低 $i$ 位，第 $1,2,3$ 个数对 $a_1,a_2,a_3$ 取模结果为 $r_1,r_2,r_3$ 的方案数。转移时只需要考虑一下三个数该位置填什么（保证异或和为 $0$）。最终 $f_{60,1,1,1,0,0,0}$ 就是答案。不过结果还需要去除掉某些数为 $0$ 的情况。只需要减去 $1+\lfloor\frac{n}{\mathrm{lcm}(a_2,a_3)}\rfloor+\lfloor\frac{n}{\mathrm{lcm}(a_1,a_3)}\rfloor+\lfloor\frac{n}{\mathrm{lcm}(a_1,a_2)}\rfloor$ 就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=998244353;
int a[3];
ll n,f[65][2][2][2][15][15][15];
ll lcm(ll x,ll y) {return x*y/__gcd(x,y)%p;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>a[0]>>a[1]>>a[2];
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            for(int k=0;k<=1;k++)
                if((i^j^k)==0) f[0][i<=(n&1)][j<=(n&1)][k<=(n&1)][i%a[0]][j%a[1]][k%a[2]]++;
    for(int t=0;t<60;t++)
        for(ll i=0;i<=1;i++)
            for(ll j=0;j<=1;j++)
                for(ll k=0;k<=1;k++)
                    for(int t1=0;t1<=1;t1++)
                        for(int t2=0;t2<=1;t2++)
                            for(int t3=0;t3<=1;t3++)
                                for(int t4=0;t4<a[0];t4++)
                                    for(int t5=0;t5<a[1];t5++)
                                        for(int t6=0;t6<a[2];t6++)
                                            if((i^j^k)==0)
                                            {
                                                int bit=n>>(t+1)&1;
                                                f[t+1][(i<=bit&&t1)||i<bit][(j<=bit&&t2)||j<bit][(k<=bit&&t3)||k<bit][((i<<(t+1))+t4)%a[0]][((j<<(t+1))+t5)%a[1]][((k<<(t+1))+t6)%a[2]]+=f[t][t1][t2][t3][t4][t5][t6]%=p;
                                            }
    ll ans=f[60][1][1][1][0][0][0];
    ans=(ans-1+p)%p;
    ans=(ans-n/lcm(a[1],a[2])%p+p)%p;
    ans=(ans-n/lcm(a[0],a[2])%p+p)%p;
    ans=(ans-n/lcm(a[0],a[1])%p+p)%p;
    cout<<ans<<'\n';
    return 0;
}

G - Rearranging

题意

给出一个 $n\times m$ 的矩阵，里面 $1\sim n$ 每个数恰好出现了 $m$ 次。现在可以重排每一行，要求最终的矩阵每列都是 $1\sim n$ 的排列。输出最终的答案矩阵，若不行，则输出 $-1$。

数据范围：$1\leq n,m\leq 100$。

题解

每行可以重排，但是一行一共有哪些数是确定的。所以可以想到这样建图：建立一张二分图，$i$ 向 $a_{i,j}$ 连边（$i$ 为左部点，$a_{i,j}$ 为右部点）。跑一次二分图最大匹配，这样就确定了第一列的答案。将这些匹配边删去，然后再继续跑最大匹配。一共跑 $m$ 次，就做完了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=105;
int a[N][N],ans[N][N];
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*N*N];
int cnt=1,head[2*N];
int s,t;
int d[2*N],cur[2*N];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
        {
            cin>>a[i][j];
            add(i,n+a[i][j],1);
        }
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++) add(s,i,1),add(i+n,t,1);
    for(int i=1;i<=m;i++)
    {
        if(dinic()<n)
        {
            cout<<"NO"<<'\n';
            return 0;
        }
        for(int j=3;j<=2*n*m+1;j+=2)
        {
            if(e[j].c==1)
            {
                ans[e[j].to][i]=e[j^1].to-n;
                e[j].c=e[j^1].c=0;
            }
        }
        for(int j=2*n*m+3;j<=cnt;j+=2)
            if(e[j].c==1)
            {
                e[j^1].c=1;
                e[j].c=0;
            }
    }
    cout<<"Yes"<<'\n';
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cout<<ans[i][j]<<" \n"[j==m];
    return 0;
}