网站做302重定向会怎么样,建设网站实训报告,怎么修改wordpress主题字体大小,赣州晒房网题意#xff1a; 给定N (1 ≤ N ≤ 10)个长度不超过6的单词,求由大写字母组成长度为L的包含至少一个给定单词的字符串有多少种,答案 mod 10007,(1 ≤ L ≤ 10^6)。 题解#xff1a; 这个题最早是在一个关于trie图的论文中看到了#xff0c;最近jzh又讲到了这个题#xff0c…题意 给定N (1 ≤ N ≤ 10)个长度不超过6的单词,求由大写字母组成长度为L的包含至少一个给定单词的字符串有多少种,答案 mod 10007,(1 ≤ L ≤ 10^6)。 题解 这个题最早是在一个关于trie图的论文中看到了最近jzh又讲到了这个题于是就把它做了~ 大致有两种做法两种方法都需要矩阵乘法加速 1、trie图中的dp 2、直接人工减少转移数量 具体做法点击这里 大致思路就是将不可能构成单词的前缀合成一类然后胡搞就行了。 View Code 1 #include iostream2 #include cstring3 #include cstdio4 #include string5 #include cstdlib6 #include algorithm7 #include map8 9 #define N 6010 #define SIZE 7011 #define mod 1000712 13 using namespace std;14 15 mapstring,int mp;16 17 int n,cnt,res,m;18 string str[N],prefix[SIZE];19 20 struct MT21 {22 int x,y;23 int mt[SIZE][SIZE];24 }zy,ans;25 26 inline MT operator *(MT a,MT b)27 {28 MT c; memset(c.mt,0,sizeof c.mt);29 c.xa.x; c.yb.y;30 for(int i1;ic.x;i)31 for(int j1;jc.y;j)32 for(int k1;ka.y;k)33 {34 c.mt[i][j]a.mt[i][k]*b.mt[k][j];35 if(c.mt[i][j]mod) c.mt[i][j]%mod;36 }37 return c;38 }39 40 inline void read()41 {42 mp.clear();43 for(int i1;in;i)44 {45 cinstr[i];46 mp[str[i]]520;47 }48 }49 50 inline bool check(string x)//检查x是否是合法的前缀 51 {52 string::size_type pos;53 for(int i1;in;i)54 {55 posx.find(str[i]);56 if(pos!x.npos) return false;57 }58 return true;59 }60 61 inline void get_det()62 {63 memset(zy.mt,0,sizeof zy.mt);64 cnt0;65 for(int i1;in;i)66 {67 string tmp;68 for(int j0;jstr[i].length();j)69 {70 tmp.push_back(str[i][j]);71 if(check(tmp)mp[tmp]0)72 {73 mp[tmp]cnt;//前缀字符串的映射 74 prefix[cnt]tmp;//前缀字符串 75 }76 }77 }78 zy.xzy.ycnt1;79 80 string tmp;81 for(int i1;icnt;i)82 for(int j0;j26;j)83 {84 tmpprefix[i]; tmp.push_back(jA);85 for(int ktmp.length();k0;k--)86 {87 if(k0)88 {89 zy.mt[cnt1][mp[prefix[i]]];//不存在后缀是已知的前缀 90 break;91 }92 else 93 {94 string tp;95 for(int ptmp.length()-k;ptmp.length();p)96 tp.push_back(tmp[p]);97 if(mp[tp]520) break;//出现单词不合法 98 else if(mp[tp]!0) {zy.mt[mp[tp]][mp[prefix[i]]];break;}//存在最大的后缀是已知的前缀 99 }
100 }
101 }
102 for(int i0;i26;i)
103 {
104 string sy;
105 sy.push_back(iA);
106 if(mp[sy]0) zy.mt[cnt1][cnt1];
107 else if(mp[sy]520) continue;
108 else zy.mt[mp[sy]][cnt1];
109 }
110
111 ans.xcnt1; ans.y1;
112 memset(ans.mt,0,sizeof ans.mt);
113 ans.mt[cnt1][1]1;
114 }
115
116 inline int qs(int a,int b)
117 {
118 int res1;
119 while(b)
120 {
121 if(b1) res(res*a)%mod;
122 a(a*a)%mod;
123 b1;
124 }
125 return res;
126 }
127
128 inline void go()
129 {
130 get_det();
131 resqs(26,m);
132 while(m)
133 {
134 if(m1) anszy*ans;
135 zyzy*zy;
136 m1;
137 }
138
139 int tmp0;
140 for(int i1;icnt1;i) tmp(tmpans.mt[i][1])%mod;
141 res-tmp;
142 printf(%d\n,(resmod)%mod);
143 }
144
145 int main()
146 {
147 while(scanf(%d%d,n,m)!EOF) read(),go();
148 return 0;
149 } 转载于:https://www.cnblogs.com/proverbs/archive/2013/02/17/2914168.html
