COCI2016 天分测试

题目:

   Lay博士想检验一下他的助手Yx是否有天分,给出一个n*m的字符矩形,并且用这个矩形无限复制拼接.
   假设当前的矩形为:

   honi
   hsin

   那么复制拼接之后就会变为:

   ......................
   ...honihonihonihoni... 
   ...hsinhsinhsinhsin... 
   ...honihonihonihoni... 
   ...hsinhsinhsinhsin... 
   ......................

   在每个方向上都是无限延伸的.
   现在Lay博士在无限的字符格子中随机选择一个起点和方向(8个方向之一),从起点开始遍历K个格子(包括起点),可以得到一个长度为K的字符串.
   他让助手Yx也按照同样方式选择,得到了另一个长度为K的字符串.
   如果两个字符串相同,那么Yx就是有天分的.
   Yx很想要通过Lay博士的检验,请帮他求出 这两个字符串相等的概率是多少,答案用分数表示.

思路:

   首先比较两个字符串是否相等,肯定是要用到哈希的。因为较小,所以只要能找到一个快速算出向某个方向延伸出的哈希值就能解决这个问题了。
   根据哈希函数的计算过程,不难发现字符串的哈希值是可以合并的,两个字符串拼接得到的哈希值就等于。所以可以预处理出哈希值的倍增数组,每次就能地快速算出向某个方向延伸出的哈希值了。

代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
#define readChar(c) do c=getchar();while(c=='\n'||c=='\r'||c==' ')
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
const int P1=1e9+7,P2=1e9+9;
const int fx[]={1,0,-1,0,1,-1,1,-1};
const int fy[]={0,1,0,-1,1,1,-1,-1};
char c[205][205];
typedef long long ll;
typedef std::pair<int,int> pii;
inline pii merge(pii a,pii b,int p1,int p2){
    pii t;
    t.first=(a.first+(ll)b.first*p1)%P1;
    t.second=(a.second+(ll)b.second*p2)%P2;
    return t;
}
pii st[205][205][8][18];
int b1[18],b2[18];
int n,m,k;
void getSt(){
    rep(x,0,n-1)
        rep(y,0,m-1)
            rep(p,0,7)
                st[x][y][p][0]=pii(c[x][y]-'a'+1,c[x][y]-'a'+1);
    b1[0]=b2[0]=27;
    rep(i,1,16){
        b1[i]=(ll)b1[i-1]*b1[i-1]%P1;
        b2[i]=(ll)b2[i-1]*b2[i-1]%P2;
    }
    int d=1;
    rep(k,1,16){
        rep(x,0,n-1)
            rep(y,0,m-1)
                rep(p,0,7){
                    int tx=((x+(ll)fx[p]*d)%n+n)%n,ty=((y+(ll)fy[p]*d)%m+m)%m;
                    st[x][y][p][k]=merge(st[x][y][p][k-1],st[tx][ty][p][k-1],b1[k-1],b2[k-1]);
                }
        d<<=1;
    }
}
pii vec[320005];
int size=0;
void getHash(int x,int y,int p,int k){
    pii ans=pii(0,0);
    int p1=1,p2=1;
    rep(i,0,16)
        if(k>>i&1){
            ans=merge(ans,st[x][y][p][i],p1,p2);
            p1=(ll)p1*b1[i]%P1;
            p2=(ll)p2*b2[i]%P2;
            x=((x+(fx[p]<<i))%n+n)%n;
            y=((y+(fy[p]<<i))%m+m)%m;
        }
    vec[++size]=ans;
}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
int main(){
//  freopen("data.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    tomin<int>(k,n/gcd(n,m)*m);
    rep(i,0,n-1)
        rep(j,0,m-1)
            readChar(c[i][j]);
    getSt();
    rep(i,0,n-1)
        rep(j,0,m-1)
            rep(p,0,7)
                getHash(i,j,p,k);
    ll down=(ll)(n*m*8)*(n*m*8),up=0;
    vec[size+1]=pii(-1,-1);
    std::sort(vec+1,vec+1+size);
    int cnt=0;
    for(int i=1;i<=size;i++){
        cnt++;
        if(vec[i]!=vec[i+1]){
            up+=(ll)cnt*cnt;
            cnt=0;
        }
    }
    ll d=gcd(down,up);
    printf("%lld/%lld\n",up/d,down/d);
    return 0;
}