BZOJ 2160: 拉拉队排练（回文树）

传送门：

　　[1]:BZOJ

　　[2]:洛谷

•题意

　　求串 s 中出现的所有奇回文串，并按照长度由大到小排序；

　　输出前 k 个奇回文串的乘积 mod 19930726;

　　如果奇回文串的个数不足 k 个，输出 -1；

•题解

　　将串 s 跑一边回文自动机；

　　将求解出的 len,cnt 数组存入一个结构体中并按照 len 由大到小排序；

　　将前 k 个奇回文串的长度相乘就行；

　　记得用快速幂，并且只要奇回文串的长度乘积；

•Code

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int MOD=;

 const int maxn=1e6+;

 int n;

 ll k;

 char s[maxn];

 struct PAM

 {

     int tot;

     int last;

     ll cnt[maxn];

     ll len[maxn];

     int fail[maxn];

     int son[maxn][];

     int newNode(int Len)

     {

         for(int i=;i < ;++i)

             son[tot][i]=;

         len[tot]=Len;

         fail[tot]=;

         cnt[tot]=;

         return tot++;

     }

     int getFail(int p,int i)

     {

         while(s[i-len[p]-] != s[i])

             p=fail[p];

         return p;

     }

     void Init()

     {

         tot=;

         last=;

         newNode();

         newNode(-);

         fail[]=;

     }

     void Count()

     {

         for(int i=tot-;i >= ;--i)

             cnt[fail[i]] += cnt[i];

     }

     void pam()

     {

         Init();

         for(int i=;i <= n;++i)

         {

             s[i]=s[i]-'a'+;

             int cur=getFail(last,i);

             if(!son[cur][s[i]])

             {

                 int now=newNode(len[cur]+);

                 fail[now]=son[getFail(fail[cur],i)][s[i]];

                 son[cur][s[i]]=now;

             }

             cnt[last=son[cur][s[i]]]++;

         }

         Count();

     }

 }_pam;

 struct Data

 {

     ll cnt;

     ll len;

     bool operator < (const Data &obj) const

     {

         return len > obj.len;

     }

 }a[maxn];

 ll qPow(ll a,ll b,ll m)

 {

     ll ans=;

     a %= m;

     while(b)

     {

         if(b&)

             ans=ans*a%m;

         a=a*a%m;

         b >>= ;

     }

     return ans;

 }

 int main()

 {

     scanf("%d%lld",&n,&k);

     scanf("%s",s+);

     s[]='#';

     _pam.pam();

     int x=;

     for(int i=;i < _pam.tot;i++)

         a[++x]=Data{_pam.cnt[i],_pam.len[i]};

     sort(a+,a+x+);

     int index=;

     ll ans=;

     while(index <= x)

     {

         if(!(a[index].len&))///坑：如果不是奇回文串，continue

         {

             index++;

             continue;

         }

         ll cur=min(k,a[index].cnt);

         ans *= qPow(a[index++].len,cur,MOD);

         ans %= MOD;

         k -= cur;

         if(k == )

             break;

     }

     if(k > )

         ans=-;

     printf("%lld\n",ans);

 }

巴特西

BZOJ 2160: 拉拉队排练（回文树）

•题意

•题解

•Code

最新文章

热门文章