NOI模拟赛(二)题解 2019-06-03

吃干饭

【问题描述】

作为区长,你有一个特殊的爱好:吃干饭。还别笑话,吃的还挺有讲究。

每一天你面前都有许多碗干饭,每次你都会选择一个区间[𝐿, 𝑅],然后选择 编号为这个区间内的若干碗干饭。在吃干饭前,你的懒政值为 0,假设你当前懒 政值为𝑥,然后吃了编号为y的干饭,那么你的懒政值会变为𝑥 ⊕ 𝑦,其中⊕符号 表示二进制异或。当然,有时候你会受到市委书记的训斥,所以你有可能良心发 作不吃干饭,也有可能你心情好吃了区间内所有的干饭。

那么,对于每一天请计算,对于所有吃干饭的方式,你的懒政值有多少种不 同的可能结果?

【输入格式】

从文件 manger.in 中读入数据。 第一行一个数𝑑𝑎𝑦𝑠,表示共有𝑑𝑎𝑦𝑠天。 接下来𝑑𝑎𝑦𝑠行,每一行两个正整数𝐿, 𝑅,满足0 ≤ 𝐿 ≤ 𝑅,意义如题所述。

【输出格式】

输出到 manger.out 中。 输出𝑑𝑎𝑦𝑠行,对于每一天输出不同结果的可能数量。

【样例输入 1】

5
0 0
233 233
7 9
15 19
36306900 36307226

【样例输出 1】

1
2
8
16
2048

【样例说明 1】

在第三天,可能的懒政值为:{0,1,6,7,8,9,14,15} 在第四天,可能的懒政值为:{0,1,2,3,12,13,14,15,16,17,18,19,28,29,30,31}

【数据规模和约定】

题解

50pts做法:

暴力把所有元素插入线性基然后答案就是\(2^{线性基大小}\)

100pts做法:

因为区间是连续的。所以当区间长度大于2时最后一位至少可以取到0和1。然后处理\([L/2,R/2]\),是一个子问题。

边界\([L,L]=2^{L=0?1:0}\)\([L,L+1]=2^{L=0?1:2}\)

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL ll gi(){ll x;int _w=scanf("%lld",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
int n;
const int maxn=500;
ll L[maxn],R[maxn],Fpw2[maxn];
namespace sub1{
    IL bool check(){
        bool flag=0;
        rep(i,1,n)if(R[i]-L[i]>10000)return false;
        return true;
    }
    ll LinerBase[100];
    IL bool Ins(ll x){
        repd(i,62,0){
            if(x>>i&1ll){
                if(!LinerBase[i]){
                    LinerBase[i]=x;return true;
                }
                x^=LinerBase[i];
            }
        }return false;
    }
    IL ll sol(int C){
        rep(i,0,60)LinerBase[i]=0;
        ll x=L[C],y=R[C];
        int ans=0;
        for(ll j=x;j<=y;++j)ans+=Ins(j);
        return Fpw2[ans];
    }
    IL void work(){
        rep(i,1,n)printf("%lld\n",sol(i));
    }
}
namespace sub2{
    IL bool check(){
        return true;
    }
    IL ll solve(ll L, ll R){
        if(L==R-1){
            return L==0?2:4;
        }
        if(L==R){
            return R==0?1:2;
        }
        return 2ll*solve(L/2ll,R/2ll);
    }
    IL ll sol(int i){
        return solve(L[i],R[i]);
    }
    IL void work(){
        rep(i,1,n) printf("%lld\n",sol(i));
    }
}
IL void prework(){
    Fpw2[0]=1ll;
    rep(i,1,60)Fpw2[i]=Fpw2[i-1]+Fpw2[i-1];
}
IL void input(){
    n=gi();
    rep(i,1,n)L[i]=gi(),R[i]=gi();
}
#ifdef LOCAL
namespace Pai{
    IL void Gen(){
        n=100;
        rep(i,1,n){
            int Len=rand()%100000;
            ll Limit=1e18;
            ll G=1ll*rand()*rand()%Limit;
            L[i]=max(0ll,G-Len);R[i]=G;
        }
    }
    IL void work(){
        rep(i,1,n){
            ll a1=sub1::sol(i);
            ll a2=sub2::sol(i);
            if(a1!=a2){
                cerr<<"[Failed on "<< i<< "]\n";
                cerr<<L[i]<<' '<<R[i]<<endl;
                cerr<<"answer1:"<<a1<<' '<<"answer2:"<<a2<<endl;
                assert(0);
            }
        }
    }
    IL void Pai(){
        rep(subtask,1,100){
            cerr<<"work on subtask:"<<subtask<<endl;
            Gen();
            work();
        }
    }
}
#endif
int main(){
    freopen("manger.in","r",stdin);
    freopen("manger.out","w",stdout);
    prework();
    input();
    if(sub1::check())sub1::work();
    else if(sub2::check())sub2::work();
    return 0;
}

仰望星空

【问题描述】

作为区长的你,当然要胸怀宇宙,所以,每天晚上你都会在市少年宫的操场 上带着孩子们仰望星空。时间久了,你便开始觉得无聊。

于是你选择了第一颗星星,以它为圆心画了一个半径为𝑅的圆并将星星分为 两类,其中圆外不包括边界上的点为第一类星星,而圆内包括边界上的点为第二 类星星。

但是你还是觉得无聊,你决定对着星空玩消消看。天上的星星可以看成是平 面上的一些点,而你每次需要找到一对星星,满足它们的类型不同,即一颗是第 一类,另一颗是第二类,然后将它们同时消去。

但是这个游戏难度太低了,你还是觉得无聊,于是你规定,每一次选出的一 对星星的连线的长度不能超过给定值𝑑。

但是这个游戏难度还是太低,于是你规定,对于每次选择的一对第一类星星 与第二类星星,它们的连线不能与两颗还没被消去的且同样距离选择的第一类星 星不超过给定值𝑑的第二类星星的连线相交。

作为一个胸怀宇宙的人,你当然希望消掉尽量多的星星。请找出任意一种消 星星的方案,使得你能消掉尽量多的星星。

【输入格式】

从文件 etoile.in中读入数据。 第一行三个正整数𝑛, 𝑅, 𝑑,𝑛表示星星的数目,𝑅, 𝑑的意义如题中所述。 接下来𝑛行,第𝑖行有两个正整数𝑥𝑖, 𝑦𝑖,表示第𝑖颗星星的坐标为(𝑥𝑖, 𝑦𝑖)。

【输出格式】

输出到 etoile.out 中。 第一行一个数2𝑘,表示你消去的星星的数目。 接下来𝑘行,每行两个数𝑥, 𝑦,表示这次操作消去了第𝑥颗星星和第y星星。

必须满足第𝒙颗星星为第一类,第𝐲颗星星为第二类。 此外,你消去的星星数目必须为最大的可能值,在方案中你的编号必须合法 且满足题面中提到的要求,你不能消去同一颗星星两次,如果你的方案任何一个 条件,你将不能获得该测试点的分数。

【样例输入 1】

10 5530 5385
8 5730
5220 61
2896 2950
1025 649
5509 1773
6057 2432
6435 975
5366 8341
1127 3616
2849 1689

【样例输出 1】

8
7 3
6 4
2 10
5 9

【样例说明 1】

注意:样例输出只是一种参考输出,如果你的输出与样例不同,答案仍然可能正确。

【数据规模和约定】

题解

不会。谁会就教一下我吧。

学外语

【问题描述】

作为法院的院长,你的特殊嗜好之一就是学外语。

你发现,不同的语言之间有着一定的联系。作为一个法学专家,你很快发现 了他们的联系。

每个语言的句子可以看成是单词的序列,而另外一个语言的表达同样意思的 句子,可以用一种很复杂的方式生成。

简单起见,假如我们把序列的长度设为𝑛,那么每个单词我们看成一个不超 过𝑛的正整数。那么另外一种语言的表达同样意思的句子的生成方式如下:选择 两个不同的不超过𝑛的正整数𝑥, 𝑦,然后交换这个序列第𝑥个位置和第y个位置的 单词,做完这个操作后,回忆单词的定义我们我们知道𝑥, 𝑦它们本身均是个单词, 所以我们进行这样一个操作,将单词𝑥原本出现的位置全部改为单词𝑦,单词𝑦原 本出现的位置全部改为单词𝑥。

当然,这个操作可以不断进行。

你想知道,给定一个初始句子,用这种方式能生成多少种不同的新的句子 呢?

由于答案过大,你只需要输出答案对 1000000007 取模的值即可。

【输入格式】

从文件 langue.in 中读入数据。 输入包含多组数据。 第一行一个数𝑇,表示数据组数。 接下来描述每一组数据。 对于每组数据第一行一个正整数𝑛,意义如题所述。 接下来一行𝑛个不超过𝑛的正整数,描述每一个单词。 输入文件不包含多于的空行。

【输出格式】

输出到 langue.out 中。 输出𝑇行,对于每组数据输出一行表示能生成的不同的新的句子的数量。

【样例输入 1】

2
3
3 1 2
10
2 9 8 6 3 4 10 5 1 7

【样例输出 1】

1
25199

【样例说明 1】

对于第一组数据,能生成的新的句子是{2,3,1}。

【样例输入输出 2】

见选手目录下的 langue / langue.in 与 langue / langue.ans。

题解

考虑把ai向i连边就可以建出一张图。稍加转换就发现交换操作等于交换图上的编号。问题变成了重编号这个图,问有多少种本质不同的图(对于i设指向它的点的标号为x[i],本质不同当且仅当有一个xi不同,其实xi就是答案的序列)。

考虑两两不同,那么就是由多个环组成的。多个环不好考虑,考虑一个环,答案是(环长减一)的阶乘。考虑多个环,由于每个环会多被算环长次(循环同构),那么答案是\(\frac{n!}{\prod_i |circle_i|}\)。但是长度相同的环其实也算同一种,所以对于相同长度的环,会被算重个数的排列次。设长度为\(i\)的环有\(num[i]\)个。

答案其实是 \[ \frac{n!}{\prod_i |circle_i| \times \prod_j (num_j!)} \] 然后考虑一下树的情况。

和环有点类似,对于任意一个点,如果它有\(P\)个子树长的一样,那么答案就要除\(P!\)。判断多少个子树"长的一样"就用树hash算一下就好了。可能姿势不太对我写了双hash。

然后考虑一下100分。

100分就是一个基环树,其实就是上面的环+树。考虑把环先扣出来,然后把环上面的每个树按照上面一档分算一下。对于长的一样的基环树,同样除一个「相同树的阶乘」。然后再考虑环上的情况。

思考一下为什么环是除一个环长,设起点为这个排列的第一个点,因为每个点是等价的,起点位于任意点所产生的方案是等价的。

那么对于一个基环,上面有一些树是等价的,我们可以找出这个环的最小循环节S,设环长为LEN,那么起点位于\(\frac{LEN}{S}\)这些块中的方案是等价的,所以答案再除一个\(\frac{LEN}{S}\)

综上,答案除一个相同子树的阶乘,相同基环树的阶乘和(环长除最小循环节)就好了。

PS:找循环节的时候把环倍长,判断\(S[0,Len]\)\(S[i,i+Len]\)这个串是否相等,如果相等意味着有一个长度为\(i\)的循环节。

贴一份由长常数巨大的代码。

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1000000007;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=2e5+10;
int n,a[maxn],T,fac[maxn],Inv[maxn];
namespace sub1{
    int rd[maxn],to[maxn],tmp[maxn];
    IL bool check(){
        return n<=8;
    }
    IL int Hash(){
        int rtn=0;
        rep(i,1,n)rtn=rtn*10+tmp[i];
        return rtn;
    }
    IL void work(){
        rep(i,1,n)to[i]=a[i];
        rep(i,1,n)rd[i]=i;
        set<int>s;
        do{
            rep(i,1,n)tmp[rd[i]]=rd[to[i]];
            s.insert(Hash());           
        }while(next_permutation(rd+1,rd+1+n));
        cout<<s.size()-1<<endl;
    }
}
namespace sub2{
    bool vis[maxn];
    IL bool check(){
        memset(vis,0,sizeof vis);
        rep(i,1,n){
            if(!vis[a[i]])vis[a[i]]=1;
            else {
                return false;
            }
        }return true;
    }
    int to[maxn];
    vector<int>G;
    void dfs(int x,int len){
        vis[x]=1;
        if(!vis[to[x]])dfs(to[x],len+1);
        else G.pb(len);
    }
    IL void work(){
        memset(vis,0,sizeof vis);
        rep(i,1,n)to[a[i]]=i;
        rep(i,1,n)if(!vis[i])dfs(i,1);
        int ans=1;
        map<int,int>S;
        for(int i=0;i<G.size();++i){
            int v=G[i];
            S[G[i]]++;
        }
        ans=fac[n];
        for(map<int,int>::iterator It=S.begin();It!=S.end();++It){
            int u=It->fr,v=It->se;
            ans=mul(ans,fpw(inv(u),v));
            ans=mul(ans,inv(fac[v]));
        }
        cout<<dec(ans,1)<<endl;
        G.clear();
        rep(i,1,n)to[i]=0;
        rep(i,1,n)vis[i]=0;
    }
}
namespace sub3{
    IL bool check(){
        rep(i,1,n)if(a[i]>i)return false;
        return true;
    }
    vector<int>e[maxn];
    bool vis[maxn];
    int In[maxn],sz[maxn];
    int ans;
    const ull base=27,base2=203;
    const int C=46,D=21,E=13,F=207;
    pair<ull,ull> dfs(int x){
        vis[x]=1;sz[x]=1;
        map<pair<ull,ull>,int>S;
        vector<ull>List1,List2;
        for(int i=0;i<e[x].size();++i){
            pair<ull,ull> t=dfs(e[x][i]);
            sz[x]+=sz[e[x][i]];
            S[t]++;
            List1.pb(t.fr);
            List2.pb(t.se);
        }   
        for(map<pair<ull,ull>,int>::iterator It=S.begin();It!=S.end();++It){
            int v=It->se;
            ans=mul(ans,inv(fac[v]));
        }
        sort(List1.begin(),List1.end());
        sort(List2.begin(),List2.end());
        
        ull Cur=sz[x];
        for(int i=0;i<List1.size();++i){
            Cur=Cur*base+List1[i]+C;
        }
        ull Cur2=sz[x]*Cur%mod;
        for(int i=0;i<List2.size();++i){
            Cur2=Cur2*base2%mod+List2[i]+F%mod;
            Cur2%=mod;
        }
        Cur2%=mod;
        pair<ull,ull> Rtn;
        Rtn=mp(Cur,Cur2);
        return Rtn;
    }
    IL void work(){
        ans=fac[n];
        rep(i,1,n)In[i]=0;
        rep(i,0,n)e[i].clear();
        rep(i,1,n)vis[i]=0;
        rep(i,1,n){
            if(a[i]==i)continue;
            else e[a[i]].pb(i);
            In[i]++;
        }
        rep(i,1,n)if(!In[i])e[0].pb(i);
        dfs(0);
        cout<<dec(ans,1)<<endl;
    }
}
IL void input(){
    n=gi();
    rep(i,1,n)a[i]=gi();
}
IL void preFac(){
    fac[0]=1;
    rep(i,1,maxn-1)fac[i]=mul(fac[i-1],i);  
    rep(i,1,maxn-1)Inv[i]=inv(i);
}
namespace Checker{
    IL void Gen3(){
        n=8;
        rep(i,1,n)a[i]=rand()%i+1;
        rep(i,1,n)cerr<<a[i]<<' ';
        cerr<<endl;
    }   
    IL void Work3(){
        srand(time(NULL));
        while(1){
            Gen3();
            sub1::work();
            sub3::work();
            cerr<<"---\n";
            system("sleep 1");
        }
    }
}
namespace sub4{
    vector<int>circle;
    vector<int>e[maxn];
    int fa[maxn],sz[maxn],vis[maxn];
    int ans,Tim;
    bool oncircle[maxn];
    IL bool check(){
        return n<maxn;
    }
    IL void fc(int x){
        vis[x]=Tim;
        for(int i=0;i<e[x].size();++i){
            int v=e[x][i];
            if(!vis[v])fc(v);
            else {
                if(vis[v]==Tim){
                    int u=x;
                    while(u!=v){
                        circle.pb(u);
                        oncircle[u]=1;
                        u=fa[u];    
                    }
                    circle.pb(v);
                    oncircle[v]=1;
                }
            }
        }
    }
    const ull base=27,base2=203;
    const int C=46,D=21,E=13,F=207;
    pair<ull,ull> workTree(int x){
        vis[x]=1;sz[x]=1;
        map<pair<ull,ull>,int>S;
        vector<ull>List1,List2;
        for(int i=0;i<e[x].size();++i){
            int v=e[x][i];
            if(oncircle[v])continue;
            pair<ull,ull> t=workTree(e[x][i]);
            sz[x]+=sz[e[x][i]];
            S[t]++;
            List1.pb(t.fr);
            List2.pb(t.se);
        }   
        for(map<pair<ull,ull>,int>::iterator It=S.begin();It!=S.end();++It){
            int v=It->se;
            ans=mul(ans,inv(fac[v]));
        }
        sort(List1.begin(),List1.end());
        sort(List2.begin(),List2.end());
        
        ull Cur=sz[x];
        for(int i=0;i<List1.size();++i){
            Cur=Cur*base+List1[i]+C;
        }
        ull Cur2=sz[x]*Cur%mod;
        for(int i=0;i<List2.size();++i){
            Cur2=Cur2*base2%mod+List2[i]+F%mod;
            Cur2%=mod;
        }
        Cur2%=mod;
        pair<ull,ull> Rtn;
        Rtn=mp(Cur,Cur2);
        return Rtn;
    }
    map<pair<ull,ull>,int>DIV;
    pair<ull,ull> Hash[maxn],H[maxn];
    ull B[maxn],G[maxn];
    IL void preWork(){
        B[0]=1;G[0]=1;
        rep(i,1,n)B[i]=B[i-1]*base,G[i]=G[i-1]*base2;
    }
    IL void workCircle(){
        if(!circle.size())return;
        vector<pair<ull,ull> >List;
        for(int i=0;i<circle.size();++i){
            pair<ull,ull>t=workTree(circle[i]);
            List.pb(t);
        }
        int SIZE=List.size();
        for(int i=0;i<SIZE;++i)List.pb(List[i]);
        Hash[2*SIZE]=mp(0,0);
        repd(i,2*SIZE-1,0)Hash[i].fr=Hash[i+1].fr*base+List[i].fr,Hash[i].se=Hash[i+1].se*base2+List[i].se;
        rep(i,0,SIZE)H[i].fr=Hash[i].fr-Hash[i+SIZE].fr*B[SIZE],H[i].se=Hash[i].se-Hash[i+SIZE].se*G[SIZE];
        DIV[*min_element(H,H+SIZE)]++;
        int loop=-1;
        rep(i,1,SIZE){
            if(SIZE%i==0&&H[0].fr==H[i].fr&&H[0].se==H[i].se){
                loop=i;
                break;
            }
        }
        assert(loop!=-1);
        ans=mul(ans,inv(SIZE/loop));
    }
    IL void work(){
        preWork();
        rep(i,1,n)fa[i]=a[i],e[a[i]].pb(i);
        ans=fac[n];
        rep(i,1,n)if(!vis[i]){
            ++Tim;
            fc(i);
            workCircle();
            circle.clear();
        }
        for(map<pair<ull,ull>,int>::iterator It=DIV.begin();It!=DIV.end();++It)ans=mul(ans,inv(fac[It->se]));
        cout<<dec(ans,1)<<endl;
        rep(i,1,n)vis[i]=0,e[i].clear(),sz[i]=0,oncircle[i]=0;
        DIV.clear();circle.clear();
    }
}
int main(){
#ifdef LOCAL
    freopen("/home/noilinux/Desktop/input.txt","r",stdin);
#endif
    freopen("langue.in","r",stdin);
    freopen("langue.out","w",stdout);
    preFac();
    T=gi();
    while(T--){
        input();
        if(sub1::check())sub1::work();  
        else if(sub2::check())sub2::work();
        else if(sub3::check())sub3::work();
        else if(sub4::check())sub4::work();
    }
    return 0;
}