题解：P17263 [ICPC 2017 Urumqi R] Friends

· · 题解

题意简述

给定 p 个函数。若一个函数子集在至少一半的自变量位置上取值全部相同，就称其为朋友圈。输出所有不能再加入其他函数的极大朋友圈，并按字典序排列。

解题思路

需要判断的是若干函数在同一位置是否取相同值。可以把函数 f_i 表示为一个含 7p 个二进制位的集合。位 (c,x) 为 1，当且仅当：

f_i(x)=c

实现时把它存入编号为 cp+x 的位。每个函数在固定位置 x 恰有一个取值，所以对应的七个位中恰有一个为 1。

对当前函数集合 S，维护所有函数位集的交：

G_S=\bigcap_{i\in S}B_i

若位 (c,x) 仍在交集中，说明 S 中每个函数在 x 处都等于 c。同一位置不可能有两个不同的值同时留下，因此 G_S 中的置位数量恰好等于所有函数取值相同的位置数量。于是朋友圈条件等价于：

2|G_S|\ge p

加入函数 v 时，只需更新：

G_{S\mathbin{\cup}\{v\}}=G_S\mathbin{\cap}B_v

这个条件具有遗传性。若某个集合已经不合法，继续加入函数只会删除交集中的位，不可能重新变为合法。因此可以在搜索中立即剪去失败分支。

使用极大集合枚举。递归状态除了当前集合 S 与交集 G_S，还维护两个函数列表：

从 C 中依次取出函数 v。加入 v 后得到新的交集，再分别过滤 C 中剩余函数和 X 中函数，只保留加入新集合后仍满足朋友圈条件的元素。递归结束后，将 v 从未处理集合移入已处理集合。

当 C 与 X 同时为空时，没有任何集合外函数能够加入当前集合，当前集合就是极大朋友圈。若 X 非空，说明已经有一个在更早分支处理过的函数仍可加入，当前集合不是极大的。函数在每层从 C 移到 X，也保证每个极大集合只会在一个分支中记录一次。

函数值不需要为每个指数重复快速幂。先迭代计算 mu^1,\mu^2,\dots,\mu^p。对每个 x，再依次将当前幂乘以 x，即可用 O(p^2) 次模运算建立全部函数位集。

搜索得到的集合使用递增函数编号保存，最后直接对整数序列排序即可得到题目要求的字典序。输入中可能重复出现相同的 (p,\mu)，所以缓存每组参数生成的完整文本。

设搜索访问的合法状态数为 K，机器字宽为 w。预处理需要 O(p^2) 时间，搜索需要 O(Kp\lceil7p/w\rceil) 位运算，空间复杂度为 O(Kp+7p^2/w)。本题 p\le100。

正确性证明

对任意函数集合 S，交集 G_S 保留的位 (c,x) 当且仅当所有函数在位置 x 都取值 c。每个位置至多保留一个值，所以 |G_S| 正好是公共取值位置数。算法使用的判定式与题目中至少一半位置相同的定义完全等价。

加入函数只会把当前交集与另一个位集取交，因此公共位置不会增加。所有被剪枝的集合及其超集都不可能成为朋友圈。递归过滤后的 C 与 X 恰好包含所有能够继续扩展当前集合的函数。

若递归在 C=X=\varnothing 时记录集合，就不存在任何可以加入的外部函数。由合法性的遗传性可知，也不存在更大的合法超集，所以记录的一定是极大朋友圈。反过来，任意极大朋友圈沿其函数在各层尚未移入 X 的分支逐个加入，所有中间集合均合法，不会被剪枝；到达完整集合时没有可扩展函数，必被记录。每层从 C 向 X 的转移又阻止相同集合从不同选择顺序重复出现。

因此搜索不重不漏地得到全部极大朋友圈。最后的标准字典序排序与题目输出顺序一致，算法正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=105;
const int M=705;
int p,u;
bitset<M> val[N];
vector<vector<int>>ans;
bool ok(const bitset<M> &f,int x)
{
    bitset<M> g=f;
    g&=val[x];
    return int(g.count())*2>=p;
}
void dfs(bitset<M> f,vector<int> &s,vector<int> c,vector<int> x)
{
    if(c.empty()&&x.empty())
    {
        ans.push_back(s);
        return;
    }
    while(c.size())
    {
        int v=c.front();
        c.erase(c.begin());
        bitset<M> g=f;
        g&=val[v];
        vector<int>nc,nx;
        for(auto i:c)
        {
            if(ok(g,i))nc.push_back(i);
        }
        for(auto i:x)
        {
            if(ok(g,i))nx.push_back(i);
        }
        s.push_back(v);
        dfs(g,s,nc,nx);
        s.pop_back();
        x.push_back(v);
    }
}
string solve()
{
    int pw[N];
    pw[0]=u;
    for(int i=1;i<p;i++)pw[i]=1LL*pw[i-1]*u%p;
    for(int i=0;i<p;i++)val[i].reset();
    for(int i=0;i<p;i++)
    {
        int v=i;
        for(int j=0;j<p;j++)
        {
            val[j][(v+pw[j])%7*p+i]=1;
            v=1LL*v*i%p;
        }
    }
    bitset<M> f;
    for(int i=0;i<7*p;i++)f[i]=1;
    vector<int>s,c,x;
    for(int i=0;i<p;i++)c.push_back(i);
    ans.clear();
    dfs(f,s,c,x);
    sort(ans.begin(),ans.end());
    ostringstream out;
    for(auto &v:ans)
    {
        for(int i=0;i<v.size();i++)
        {
            if(i)out<<' ';
            out<<v[i];
        }
        out<<'\n';
    }
    return out.str();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<pii,string>mem;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>p>>u;
        pii key={p,u};
        if(!mem.count(key))mem[key]=solve();
        cout<<mem[key]<<"END"<<'\n';
    }
    return 0;
}