题解:

(我这个大傻叉连这题都不会做了)

首先肯定是转移了...

我们单独考虑每个球,变化的概率都是$\frac{1}{m}$.

于是令$f_i$表示编号为$i$的球的个数,考虑一次操作$f_i$的变化.

考虑单个标号为$i$的球对$f_i$的影响:$\frac{1}{m}\times{0}+(1-\frac{1}{m})\times{1}$

考虑单个标号为$i-1$的球对$f_i$的影响:$\frac{1}{m}\times{1}+(1-\frac{1}{m})\times{0}$

然后我们就搞出了转移矩阵.

有意思的是,这是一个循环矩阵!

也就是说,从第二行开始,每一行都是上一行右移一位得到的.

显而易见,循环矩阵的乘积依然是循环矩阵.

所以我们只要暴力算出第一行就行了,所以可以$O(n^2)$暴力,也可以利用FFT优化至$O(nlogn)$.

这样的话就能做这道题目了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 1010
int n,m,k,a[N];
struct Vector{
    f2 line[N],row[N];
    inline void operator*=(const Vector&B){
        static f2 _line[N];
        int i,j,k;
        for(i=0;i<n;++i)
            _line[i]=0;
        for(i=0;i<n;++i)
            for(j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
                _line[i]+=line[k]*B.row[j];
        for(i=0;i<n;++i)
            line[i]=_line[i];
        for(i=0;i<n;++i)
            row[(n-i)%n]=line[i];
    }
}t,re;
int main(){
    cin>>n>>m>>k;
    int i,j;
    for(i=0;i<n;++i)
        scanf("%d",&a[i]);
    re.line[0]=re.row[0]=1;
    t.line[0]=(f2)(m-1)/m;
    t.line[1]=1.0/m;
    t.row[0]=(f2)(m-1)/m;
    t.row[n-1]=1.0/m;
    for(;k;k>>=1,t*=t)
        if(k&1)
            re*=t;
     
    f2 ans;
    for(i=0;i<n;++i){
        for(ans=0,j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
            ans+=a[k]*re.row[j];
        printf("%.3lf\n",ans);
    }
    return 0;
}

题解:

我们单独考虑每个格子,如果这个格子在一次染色中不被染色的概率为$p$,则这个格子在$k$次染色中被染色的概率就是$1-p^k$.

对于每个格子如何求$p$:

看着代码自己脑补一下吧= =

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
typedef long long ll;
 
ll calc(int n,int m){
    return(ll)n*m*n*m;
}
 
ll C[1010][1010];
int main(){
    int k,w,h;
    cin>>k>>w>>h;
    ll total;
    f2 ans=0;
    for(int i=0;i<=w;++i)
        for(int j=0;j<=h;++j)
            C[i][j]=calc(i,j);
    for(int i=1;i<=w;++i){
        for(int j=1;j<=h;++j){
            total=0;
            total-=C[i-1][j-1]+C[i-1][h-j]+C[w-i][j-1]+C[w-i][h-j];
            total+=C[w][j-1]+C[w][h-j]+C[i-1][h]+C[w-i][h];
            ans+=1-pow((f2)total/C[w][h],k);
        }
    }
    cout<<(ll)ans+(ans-(ll)ans>=.5?1:0)<<endl;
    return 0;
}

思路:

首先考虑如果一个串固定时,如何求出最多的出现次数.

当模式串存在覆盖关系时,很显然可以舍弃掉一些.那么现在所有的串之间都不存在覆盖关系.

那么我们可以从前向后扫描,如果出现一个完整的模式串,答案加1,同时将指针移到下一个位置继续刚才的操作.

由于不存在覆盖关系,这样的贪心是很显然的,不信的话可以自己画图看看.

考虑将模式串建成AC自动机.令\(P[i][j]\)表示串长为\(i\),现在处于AC自动机上的节点\(j\)上的概率.这个很容易用矩阵乘法搞定.

那么我们的答案是是什么呢?

考虑从某个节点转移到某个完全包含某个模式串的节点,那么此时答案+1,同时状态回到根节点.我们只要在矩阵中加一维计数器来搞就行了.

其实没说什么= =  不懂自己看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int ch[80][26],fail[80],end[80],cnt,q[80],fr,ta;
 
char s[20],sav[6][20];int len[6];bool covered[6];
 
typedef long double f4;
 
struct Matrix{
    f4 d[81][81];int w,h;
    Matrix(){}
    Matrix(int _w,int _h):w(_w),h(_h){}
     
    void operator*=(const Matrix&B){
        register int i,j,k;
        Matrix res(w,B.h);
        for(i=0;i<res.w;++i)for(j=0;j<res.h;++j){
            res.d[i][j]=0;for(k=0;k<h;++k)res.d[i][j]+=d[i][k]*B.d[k][j];
        }
        *this=res;
    }
};
 
bool cover(int a,int b){
    if(len[a]<len[b])return 0;
    register int i,j;
    for(i=1;i+len[b]-1<=len[a];++i){
        bool ok=1;
        for(j=1;j<=len[b];++j)if(sav[a][i+j-1]!=sav[b][j])ok=0;
        if(ok)return 1;
    }
    return 0;
}
 
int main(){
    int n,L,k;scanf("%d%d%d",&n,&L,&k);register int i,j;
     
    for(i=1;i<=n;++i)scanf("%s",sav[i]+1),len[i]=strlen(sav[i]+1);
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(cover(i,j))covered[i]=1;
     
    bool allcovered=1;for(i=1;i<=n;++i)if(!covered[i])allcovered=0;
    if(allcovered)covered[1]=0;
     
    int p,y;
    for(i=1;i<=n;++i)if(!covered[i]){
        p=0;for(j=1;j<=len[i];++j){if(!ch[p][y=sav[i][j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
        end[p]=1;
    }
     
    for(j=0;j<k;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<k;++j){
            if((v=ch[u][j])){
                q[ta++]=v;
                for(r=fail[u];r&&!ch[r][j];r=fail[r]);
                end[v]|=end[fail[v]=ch[r][j]];
            }else ch[u][j]=ch[fail[u]][j];
        }
    }
     
    Matrix res(1,cnt+2);res.d[0][0]=1;
     
    Matrix add(cnt+2,cnt+2);add.d[cnt+1][cnt+1]=1;
    for(i=0;i<=cnt;++i){
        for(j=0;j<k;++j){
            if(end[ch[i][j]])add.d[i][cnt+1]+=(f4)1/k,add.d[i][0]+=(f4)1/k;
            else add.d[i][ch[i][j]]+=(f4)1/k;
        }
    }
     
    for(;L;L>>=1,add*=add)if(L&1)res*=add;
     
    double output=res.d[0][cnt+1];
    printf("%.6lf",output);
     
     
    return 0;
}

思路:
首先\(O(n^3)\)的思路非常朴素,只需要考虑每条向量的贡献即可.向量的出现概率即为这两个点出现且向量右侧的点均不出现.于是我们需要暴力\(O(n)\)check右侧的点是否均不出现.

我们考虑以一个点为起点的所有向量的答案.

那么对于每一个向量右侧的点必定都是一段区间,且满足单调性.

我们枚举起点,然后把剩下的点按照关于起点的极角序排序,然后依次扫描即可.

当然有几个坑点:

概率有一些为0的不能直接乘除,而需要记录零的个数.

还有就是坑爹的三点共线问题.

我们考虑当角度相同时,按照距离从大到小排序.

然后扫描的时候进行一些特判.这里没太弄明白就先挖坑了.

(好像一开始先把点随机扰动一下应该也可以吧)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 1010
struct Point{
    f2 x,y,p;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
}P[N];
inline f2 sqr(const f2&x){return x*x;}
inline f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
inline f2 dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;}
inline f2 length(const Point&a){return sqrt(sqr(a.x)+sqr(a.y));}
 
static const f2 eps=1e-8;
inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);}
 
struct Seg{
    Point v;
    f2 Ang,area,p,len;
    inline bool operator<(const Seg&B)const{
        return dcmp(Ang-B.Ang)==0?len>B.len:Ang<B.Ang;
    }
}S[N];
 
int main(){
    int n;scanf("%d",&n);register int i,j,k;
    for(i=0;i<n;++i)scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].p),P[i].p/=1000.0;
    f2 ans=0;
    for(i=0;i<n;++i){
        int id=0;
        for(j=0;j<n;++j)if(i^j){
            S[id].v=P[i]-P[j];
            S[id].Ang=atan2(S[id].v.y,S[id].v.x);
            S[id].area=cross(P[i],P[j]);
            S[id].p=P[j].p;
            S[id].len=length(S[id].v);
            id++;
        }
        sort(S,S+id);
        long double nowp=P[i].p;
        int zero=0;
        for(j=0;j<id;++j)if(dcmp(S[j].p-1)==0)++zero;else nowp*=(1-S[j].p);
         
        k=0;
        for(j=0;j<id;++j){
            while(dcmp(cross(S[j].v,S[k].v))>0||(dcmp(cross(S[j].v,S[k].v))==0&&dcmp(dot(S[k].v,S[j].v-S[k].v))<=0)){
                if(dcmp(1-S[k].p))nowp/=1-S[k].p;else --zero;
                k=(k+1)%id;
                if(k==j)break;
            }
            if(!zero)ans+=S[j].area*nowp*S[j].p;
            if(dcmp(1-S[j].p)!=0)nowp*=(1-S[j].p);else ++zero;
        }
    }
     
    printf("%.6lf",ans*.5);
    return 0;
}