M_sea

UVA12387 Alphabet Soup
UVaLuoguVjudge分析考虑 Polya 定理。容易得到一个置换的循环个数是 $\gcd(k,P)$ 。于...
扫描右侧二维码阅读全文
07
2019/09

UVA12387 Alphabet Soup

UVa

Luogu

Vjudge

分析

考虑 Polya 定理。容易得到一个置换

$$ \left(\begin{matrix}1&2&3&\cdots&P\\k&k+1&k+2&\cdots&k-1\end{matrix}\right) $$

的循环个数是 $\gcd(k,P)$ 。

于是我们只需要找出所有置换即可。

可以使用 KMP 。把原数组倍长,然后求差分数组。于是直接拿原差分数组匹配,能够匹配上的位置就对应着一个置换。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=720000+10;
const int mod=100000007;

inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,m,cnt,ans;
int a[N],b[N],nxt[N];

inline void get_next() {
    for (re int i=2,j=0;i<n;++i) {
        while (j&&b[j+1]!=b[i]) j=nxt[j];
        if (b[j+1]==b[i]) ++j;
        nxt[i]=j;
    }
}

inline void kmp() { cnt=0;
    for (re int i=1,j=0;i<n<<1;++i) {
        while (j&&b[j+1]!=a[i]) j=nxt[j];
        if (b[j+1]==a[i]) ++j;
        if (j==n-1)
            ++cnt,ans=(ans+qpow(m,__gcd(n,i-n)))%mod,j=nxt[j];
    }
    ans=1ll*ans*qpow(cnt,mod-2)%mod;
}

int main() {
    while (m=read(),n=read()) {
        if (m==-1&&n==-1) break;
        if (n==1) { printf("%d\n",m); continue; }
        for (re int i=1;i<=n;++i) a[i]=read();
        sort(a+1,a+n+1);
        for (re int i=1;i<=n;++i) a[i+n]=a[i]+360000;
        for (re int i=n<<1;i;--i) a[i]-=a[i-1];
        for (re int i=2;i<=n;++i) b[i-1]=a[i];
        ans=0,get_next(),kmp();
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 07 日 09 : 56 PM

1 条评论

  1. xgzc

    Polya!

发表评论