牛客多校9 B(概率dp+差分)G(回文自动机+双哈希)

B
题意：n个点，每个点最远跳到距离自己ai，ai取值于[1,n-i]的点上。

问：两人从第一个点跳到第n个点上花费相同步数的概率是多少。

dp[i][j]可以设为：走到i位置上花费了j步的概率，，，你说为什么这么设，，，我不到啊，我一眼就这么写的。

交换一下两个维度，dp变为dp[j][i]
显然有这样的思想
第j+1步可以使得当前节点能到的所有节点概率变为：原数值+dp[j][i]*1/a[i]

那么对于区间同时加一个数的问题显然可以差分+前缀和优化求解。

整道题也就基本结束了。

#include 
using namespace std;
#define int long long
const int mod = 998244353;

int dp[8050][8050],a[10500];
int inv[10050];
int fastpow(int n,int a)
{
    int res=1;
    while(n)
    {
        if(n&1)
            res=res*a%mod;
        n>>=1;
        a=a*a%mod;
    }
    return res%mod;
}
signed main()
{
    inv[1]=1;
    for(int i=2;i<=10000;i++)
        inv[i]=fastpow(mod-2,i);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[0][1]=1;
    for(int j=0;j<=n;j++)
    {
        if(j)
        {
            for(int i=1;i<=n;i++)
            {
                dp[j][i]=(dp[j][i]+dp[j][i-1])%mod;
            }
        }
        for(int i=1;i<=n;i++)
        {
            dp[j+1][i+1]=(dp[j+1][i+1]%mod+dp[j][i]*inv[a[i]]%mod)%mod;
            dp[j+1][i+a[i]+1]=(dp[j+1][i+a[i]+1]%mod-inv[a[i]]*dp[j][i]%mod)%mod;
        }
    }
    int sum=0,sq=0;
    for(int j=1;j<=n;j++)
    {
        sum+=dp[j][n];
        sum%=mod;
        sq+=dp[j][n]*dp[j][n];
        sq%=mod;
    }
    sum=sum*sum%mod;
    int ans=sq*fastpow(mod-2,sum);
    cout<<ans%mod<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

G
题意：求n个字符串的本质不同公共回文子串个数。

思路：回文自动机可以求出每个字符串的所有本质不同回文子串，我们可以通过DFS来获取相对应串的哈希值，显然，如果一个哈希重复出现了k次，那么说明这k个字符串都含有这个回文子串。

具体操作就是对于每个字符串都构造一次PAM然后都做一次DFS存储hash值。

但是你这么做之后会发现：WA了。

怎么回事呢，原来是自然溢出和单哈希都是会有冲突情况发生的。
这样我们用双哈希来写，降低冲突发生的概率到极低即可。

#include 
#define int long long
using namespace std;
const int N = 1e6+100;
const int mod =1e9+7;
int has1[N];
int has2[N];
char s[N];
int p1[N];
int p2[N];
map<pair<int,int>,int> mp;
struct Palindromic_Tree
{
    int trie[N][26];//trie指针，trie指针和字典树类似，指向的回文子串为i节点对应的回文子串两端加上同一个字符ch构成
    int fail[N];//fail指针，失配后跳转到fail指针指向的节点，fail指针指向的是i节点对应的回文子串的最长后缀回文子串（是真后缀），这个匹配过程与kmp有点类似，fail[i]表示节点i失配以后跳转到长度小于该串且以该节点表示回文串的最后一个字符结尾的最长回文串表示的节点
    int cnt[N];//在调用count函数之后，cnt[i]表示i节点对应的回文子串的出现次数的准确值
    int num[N];//在调用add函数之后返回num[last]可以得到以i位置的字符为尾的回文串个数
    int len[N];//len[i]表示节点i表示的回文串的长度
    int S[N];//存放添加的字符,
    int last;//指向上一个字符所在的节点，方便下一次add
    int n;//字符数组指针，从1开始，到n结束
    int p;//节点指针，0指向偶根，1指向奇根，有效编号到p-1
    int newnode(int l)
    {//新建节点
        for(int i=0;i<26;++i)
            trie[p][i] = 0;
        cnt[p]=0;
        num[p]=0;
        len[p]=l;
        fail[p]=0;
        return p++;
    }
    void init()
    {
        p=0;
        newnode(0);newnode(-1);
        last=0;
        n=0;
        S[n]=-1;//开头放一个字符集中没有的字符，减少特判
        fail[0]=1;
    }
    int get_fail(int x) //和KMP一样，失配后找一个尽量最长的
    {
        while(S[n-len[x]-1]!=S[n])
            x=fail[x];
        return x;
    }
    void add(int c)
    {
        c-='a';
        S[++n]=c;
        int cur=get_fail(last);//通过上一个回文串找这个回文串的匹配位置
        if (!trie[cur][c]) //如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
        {
            int now=newnode(len[cur]+2);//新建节点
            fail[now]=trie[get_fail(fail[cur])][c];//和AC自动机一样建立fail指针，以便失配后跳转
            trie[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }
        last=trie[cur][c];
        cnt[last]++;
    }
    void get_cnt()
    {
        for(int i=p-1;i>=0;--i)
            cnt[fail[i]] += cnt[i];
    }
}pt;
int ans,k;
void DFS(int x,int len)
{
    for(int i=0;i<26;i++)
    {
        if(pt.trie[x][i]==0)
            continue;
        if(x==1)
        {
            has1[pt.trie[x][i]]=(i+1)%mod;
            has2[pt.trie[x][i]]=(i+1)%mod;
            mp[{has1[pt.trie[x][i]],has2[pt.trie[x][i]]}]++;
            if(mp[{has1[pt.trie[x][i]],has2[pt.trie[x][i]]}]==k)
                ans++;
            DFS(pt.trie[x][i],len+1);
        }
        else
        {
            has1[pt.trie[x][i]]=(has1[x]*131%mod+(i+1)%mod+(i+1)*p1[len+1]%mod)%mod;
            has2[pt.trie[x][i]]=(has2[x]*13331%mod+(i+1)%mod+(i+1)*p2[len+1]%mod)%mod;
            mp[{has1[pt.trie[x][i]],has2[pt.trie[x][i]]}]++;
            if(mp[{has1[pt.trie[x][i]],has2[pt.trie[x][i]]}]==k)
                ans++;
            DFS(pt.trie[x][i],len+2);
        }
    }
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    p1[0]=p2[0]=1;
    for(int i=1;i<N;i++)
    {
        p1[i]=131*p1[i-1]%mod;
        p2[i]=13331*p2[i-1]%mod;
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        pt.init();
        cin>>(s+1);
        int len=strlen(s+1);
        for(int i=1;i<=len;i++)
            pt.add(s[i]-'a');
        DFS(1,0);
        DFS(0,0);
        for(int i=0;i<=pt.p+1;i++)
        {
            has1[i]=0;
            has2[i]=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

不要这么写！！！