在一个城市做相亲网站,马蹄网室内设计,wordpress破解主题,wordpress中文标签件文章目录titlesolutioncodetitle
solution
针对数据编程才是坠吊的#xff01;#xff01;#xff01; 观察数据#xff0c;发现分隔数据的LLL跨度过大#xff0c;没有衔接——推测很有可能是分数据做法 ①#xff1a;考虑L≤100L\le100L≤100的情况 可以暴力DPDPDP转移…
文章目录titlesolutioncodetitle
solution
针对数据编程才是坠吊的 观察数据发现分隔数据的LLL跨度过大没有衔接——推测很有可能是分数据做法 ①考虑L≤100L\le100L≤100的情况 可以暴力DPDPDP转移 设dp[i][j]:dp[i][j]:dp[i][j]: 长度为iii指向自动机上jjj节点的方案数 枚举基本串kkk写个find()find()find()函数暴力找jjj节点跳基本串kkk后指向的节点tototo dp[ilen[k]][to](dp[ilen[k]][to]dp[i][j])%moddp[ilen[k]][to](dp[ilen[k]][to]dp[i][j])\%moddp[ilen[k]][to](dp[ilen[k]][to]dp[i][j])%mod O(L3)O(L^3)O(L3)完全可以非常可以很好很好 ②考虑基本串的长度只有1/21/21/2
思考一 此时LLL急速飙升一般上了1e7,1e8,1e91e7,1e8,1e91e7,1e8,1e9的数据点不是有规律周期可循就是n,logn\sqrt n,lognn,logn 这里因为长度特别小加上之前的做题经验知道ACACAC自动机套矩阵快速幂的套路 于是自然而然就往矩阵加速方面靠了
思考二 对于长度为lenlenlen的一个串sss只有可能是由长度为s−1s-1s−1的一个固定的串s′ss′或者长度为s−2s-2s−2的一个固定的串s′′ss′′转移而来 如果借用上面的dpdpdp思路应该dp[len][to](dp[len−1][j]dp[len−2][k])%moddp[len][to](dp[len-1][j]dp[len-2][k])\%moddp[len][to](dp[len−1][j]dp[len−2][k])%mod 这个狮子不仅代表的是转移方程也在暗示每个状态只会与之前的最多两个状态挂钩 眼尖的犇犇更会发现有点像斐波拉契递推式——此时也会联想到矩阵加速求解 有长度为111的基本串也有长度为222的基本串矩阵要扩大两倍 也可以理解为把N×NN\times NN×N的一个矩阵看成一项fif_ifi可以类比斐波拉契的转移推导过程
PS:下面的nnn仅代表一个字符含义并不是题目里的nnn
初始矩阵OOO (x0x1x2..xnx0′x1′..xn′)\begin{pmatrix} x_0\\ x_1\\ x_2\\ .\\ .\\ x_n\\ x_0\\ x_1\\ .\\ .\\ x_n \end{pmatrix}⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛x0x1x2..xnx0′x1′..xn′⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞ 我们想让ta转移成 (x0′x1′x2′..xn′x0′′x1′′..xn′′)\begin{pmatrix} x_0\\ x_1\\ x_2\\ .\\ .\\ x_n\\ x_0\\ x_1\\ .\\ .\\ x_n \end{pmatrix}⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛x0′x1′x2′..xn′x0′′x1′′..xn′′⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞
code
#include queue
#include cstdio
#include cstring
using namespace std;
#define int long long
#define mod 1000000007
int n, m, L, tot;
char s[105];
int len[55];
int dp[105][105];
char S[55][105];queue int q;struct node {int trie[105][30], fail[105];bool End[105];void insert() {int now 0, Len strlen( s );for( int i 0;i Len;i ) {int nxt s[i] - a;if( ! trie[now][nxt] ) trie[now][nxt] tot;now trie[now][nxt];}End[now] 1;}void Fail() {memset( fail, 0, sizeof( fail ) );while( ! q.empty() ) q.pop();fail[0] 0;for( int i 0;i 26;i )if( trie[0][i] ) {fail[trie[0][i]] 0;q.push( trie[0][i] );}while( ! q.empty() ) {int now q.front(); q.pop();End[now] | End[fail[now]];for( int i 0;i 26;i ) {if( trie[now][i] ) {fail[trie[now][i]] trie[fail[now]][i];q.push( trie[now][i] );}elsetrie[now][i] trie[fail[now]][i];}}}int find( int now, int id ) {//求从now开始跳id串后指向的节点for( int i 0;i len[id];i ) {now trie[now][S[id][i] - a];if( End[now] ) return -1;}return now;/*这种写法是错误的从End[now]处理的是从根节点到now这一条串的路上是否含有一个被禁止的子串从被禁止的子串开始往下跳不算for( int i 0;i len[id];i ) {if( End[now] ) return -1;else now trie[now][S[id][i] - a];}if( End[now] ) return -1;else return now;*/}}AC;struct Matrix {int c[205][205];Matrix() {memset( c, 0, sizeof( c ) );}Matrix operator * ( const Matrix p ) const {Matrix ans;for( int i 0;i ( tot 1 | 1 );i )for( int k 0;k ( tot 1 | 1 );k )if( c[i][k] )for( int j 0;j ( tot 1 | 1 );j )ans.c[i][j] ( ans.c[i][j] c[i][k] * p.c[k][j] % mod ) % mod;return ans;}}O, V;Matrix qkpow( Matrix x, int y ) {Matrix ans;for( int i 0;i ( tot 1 | 1 );i )ans.c[i][i] 1;while( y ) {if( y 1 ) ans ans * x;x x * x;y 1;}return ans;
}
//dp[i][j]:长度为i指向自动机上j的方案数
void subtask1() {dp[0][0] 1;for( int i 0;i L;i ) { for( int j 0;j tot;j ) {if( ! dp[i][j] ) continue;for( int k 1;k n;k ) {int to AC.find( j, k ); if( ! ( ~ to ) || i len[k] L ) continue;else dp[i len[k]][to] ( dp[i len[k]][to] dp[i][j] ) % mod;}}}int ans 0;for( int i 0;i tot;i ) ans ( ans dp[L][i] ) % mod;printf( %lld\n, ans );
}void subtask2() {O.c[0][0] 1;for( int i 0;i tot;i )V.c[i tot 1][i] 1;for( int i 0;i tot;i ) {for( int j 1;j n;j ) {int to AC.find( i, j );if( ! ( ~ to ) ) continue;if( len[j] 1 ) {V.c[i tot 1][to tot 1] ;if( ! i ) O.c[0][to tot 1] ;}elseV.c[i][to tot 1] ;}}O O * qkpow( V, L );int ans 0;for( int i 0;i tot;i )ans ( ans O.c[0][i] ) % mod;printf( %lld\n, ans );
}signed main() {scanf( %lld %lld %lld, n, m, L );for( int i 1;i n;i )scanf( %s, S[i] ), len[i] strlen( S[i] );for( int i 1;i m;i ) {scanf( %s, s );AC.insert();}AC.Fail();if( L 100 ) subtask1();else subtask2();return 0;
}
