#uoj 442 【集训队作业2018】观众小p

· · 个人记录

题意清楚明白,此处不再赘述了

本题题解

为了方便起见，我们认为0代表P也就是布，1代表R也就是石头,2代表S也就是布，这样的话我们是按照字典序给石头剪刀布标号的

看到这种不知道怎么下手数据范围还贼大的题第一反应一定是打表

我们不妨设dp(i,j)表示当2^i个沙雕玩石头剪刀布并且胜利者是一个j型沙雕，此时有多少个0,1,2型沙雕参加了比赛，也就是说一个状态是一个三元组

那么我们可以很轻易的列出转移方程dp(i,j)=dp(i-1,j)+dp(i-1,(j+1)\%3),很显然,如果j型沙雕胜利了，那么最后一场比赛的沙雕类型也就确定了

通过这个转移方程你也发现了，对于一个n，只有三种可能的参加比赛人数

那么我们不如打个表康康这个dp数组有什么规律

n=1
win 0:1 1 0
win 1:0 1 1
win 2:1 0 1
n=2
win 0:1 2 1
win 1:1 1 2
win 2:2 1 1
n=3
win 0:2 3 3
win 1:3 2 3
win 2:3 3 2
n=4
win 0:5 5 6
win 1:6 5 5
win 2:5 6 5
n=5
win 0:11 10 11
win 1:11 11 10
win 2:10 11 11
n=6
win 0:22 21 21
win 1:21 22 21
win 2:21 21 22
n=7
win 0:43 43 42
win 1:42 43 43
win 2:43 42 43
n=8
win 0:85 86 85
win 1:85 85 86
win 2:86 85 85
n=9
win 0:170 171 171
win 1:171 170 171
win 2:171 171 170
n=10
win 0:341 341 342
win 1:342 341 341
win 2:341 342 341
n=11
win 0:683 682 683
win 1:683 683 682
win 2:682 683 683
n=12
win 0:1366 1365 1365
win 1:1365 1366 1365
win 2:1365 1365 1366
n=13
win 0:2731 2731 2730
win 1:2730 2731 2731
win 2:2731 2730 2731
n=14
win 0:5461 5462 5461
win 1:5461 5461 5462
win 2:5462 5461 5461
n=15
win 0:10922 10923 10923
win 1:10923 10922 10923
win 2:10923 10923 10922
n=16
win 0:21845 21845 21846
win 1:21846 21845 21845
win 2:21845 21846 21845
n=17
win 0:43691 43690 43691
win 1:43691 43691 43690
win 2:43690 43691 43691
n=18
win 0:87382 87381 87381
win 1:87381 87382 87381
win 2:87381 87381 87382

稍微瞪几眼之后就会发现各类沙雕的数目大致相等,并且总有一个数字和另外两个数字差1，那么我们尝试着从这个与众不同的数字来倒推胜利者的编号，

那么很快就会发现假设j型沙雕的参加人数与众不同，那么(j+n)\%3型沙雕一定会胜利

以上结论的证明都可以使用数学归纳法，此处不再赘述

那么首先我们先解决怎么判无解的问题,容易发现n给定了之后，出现数字的集合是一样的，那么我们可以在模一个质数的意义下计算出每个数字出现了几次，然后和输入的数字比较是否完全一致即可

蛤？会被叉？多做几个模数搞几遍不就行了

其实直接写个高精度就行了，不过我懒

现在判完无解了让我们来考虑如何构造字典序最少的方案

容易看出如果有2^n个沙雕打比赛，那么只有3种本质不同的沙雕序列,此时我们可以对这些沙雕建一个竞赛树，那么我们事实上只需要计算出son(n,j,0/1)表示当2^n个沙雕打比赛并且第j个沙雕获胜的时候，前一半沙雕比赛最后的胜者是谁以及后一半沙雕的胜者是谁即可

那么这就非常简易了，根据贪心的想法我们只需要选择字典序小的字符串作为左儿子和字典序大的字符串作为右儿子即可，因为两个字符串绝对不可能相同

那么不妨设rk(n,j)表示2^n个沙雕打比赛并且j型沙雕的赢了的时候这个字符串在三个合法序列之中的相对大小，这时候比较两个字符串就只需要比较前一半(左儿子)是否相等,如果一样就比较右儿子,而长度为2^{n-1}的序列大小关系保存在rk(n-1,j)里，上一轮已经求出来了

那么我们就把这个竞赛树建出来了，那么输出hash值就是简单的递推即可，而输出l,r之间的序列可以直接大力在竞赛树上dfs

至于如何定位区间嘛，显然我们可以先定位到l这个节点上(直接按照二进制位走就完了)，然后接下来按照dfs序输出字符，如果走到了r就直接退出，关键的问题是如何记录当前输出到了序列的第几位

在膜998244353意义记录就行了，显然输出区间的长度远远小于998244353，编号并不会冲突

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e5+10;typedef long long ll;const ll mod=998244353;
const ll md[5]={998244353,(ll)1e9+7,(ll)1e9+9,998244853,469762049};
int s[N][3][2];ll dp[N][3];int rk[3];
struct data
{
    int u;int v;int id;
    friend bool operator <(data a,data b)
    {return (rk[a.u]!=rk[b.u])?rk[a.u]<rk[b.u]:rk[a.v]<rk[b.v];}
}srt[3];int n;int op;char* lf;int ctt;int ed;
# define md(x) (x=(x>=mod)?x-mod:x)
inline void dfs(int dep,int id,int mrk)
{
    if(dep==0)
    {
        switch(id)
        {
            case 0:{putchar('P');break;}
            case 1:{putchar('R');break;}
            case 2:{putchar('S');break;}
        }ctt++;md(ctt);return;
    }
    if(lf[n-dep+1]=='1'&&mrk){if(ctt!=ed)dfs(dep-1,s[dep][id][1],mrk);}
    else 
    {
        if(ctt!=ed){dfs(dep-1,s[dep][id][0],mrk);}
        if(ctt!=ed){dfs(dep-1,s[dep][id][1],0);}
    }
}
inline ll po(ll a,ll p,ll mod){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
struct bigu
{
    char mde[N];int len;int bas;
    inline void ih(){scanf("%s",mde+1);len=1;while(mde[len+1]!='\0')len++;}
    inline ll gval(ll mod){ll ret=0;for(int i=1;i<=len;i++)ret=(ret*bas+mde[i]-'0')%mod;return ret;}
}c[3],b1,b2;ll typ1[3];ll typ2[3];
int main()
{
    c[0].bas=c[1].bas=c[2].bas=10;b1.bas=2;b2.bas=2;
    scanf("%d%d",&n,&op);c[1].ih();c[2].ih();c[0].ih();int rem=po(2,n,3);
    for(int i=0;i<5;i++)
    {
        ll pw=po(2,n,md[i]);ll iv3=po(3,md[i]-2,md[i]);
        //printf("pw=%lld,iv3=%lld\n",pw,iv3);
        if(rem==1)typ2[0]=typ2[1]=(pw+md[i]-1)*iv3%md[i],typ2[2]=(pw+2)*iv3%md[i];
        if(rem==2)typ2[0]=typ2[1]=(pw+1)*iv3%md[i],typ2[2]=(pw+md[i]-2)*iv3%md[i];
        //for(int j=0;j<3;j++)printf("%lld ",typ2[j]);printf("\n");
        for(int j=0;j<3;j++)typ1[j]=c[j].gval(md[i]);sort(typ2,typ2+3);sort(typ1,typ1+3);
        for(int j=0;j<3;j++)if(typ2[j]!=typ1[j]){printf("-1\n");return 0;}
    }int rt=0;
    for(int i=0;i<3;i++)
    {
        ll nw=c[i].gval(md[4]);int cnt=0;
        for(int j=0;j<3;j++)cnt+=(nw==typ2[j]);if(cnt==1)rt=i;
    }(rt+=n)%=3;for(int i=0;i<3;i++)rk[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<3;j++)
        {
            int s1=j;int s2=(j+1)%3;if(rk[s1]>rk[s2])swap(s1,s2);
            s[i][j][0]=s1;s[i][j][1]=s2;srt[j]=(data){s1,s2,j};
        }sort(srt,srt+3);for(int j=0;j<3;j++)rk[srt[j].id]=j;
    }
    if(op!=2)
    {
        dp[0][0]='P';dp[0][1]='R';dp[0][2]='S';ll pw=233;
        for(int i=1;i<=n;i++,pw=pw*pw%mod)
            for(int j=0;j<3;j++)dp[i][j]=(dp[i-1][s[i][j][0]]+pw*dp[i-1][s[i][j][1]])%mod;
        printf("%lld\n",dp[n][rt]);
    }
    if(op!=1)
    {
        b1.ih();b2.ih();ctt=(b1.gval(mod)+mod-1)%mod;ed=b2.gval(mod);
        lf=b1.mde;dfs(n,rt,1);
    }return 0;
}