NC50359. 文本生成器
描述
输入描述
输入的第一行包含两个正整数，分别是使用者了解的单词总数N，GW文本生成器v6生成的文本固定长度M；
以下N行，每一行包含一个使用者了解的单词。
输出描述
一个整数，表示可能的文章总数。只需要知道结果模10007的值。
示例1
输入:
2 2 A B
输出:
100
Java(javac 1.8) 解法, 执行用时: 588ms, 内存消耗: 44916K, 提交时间: 2021-03-07 20:06:17
import java.io.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;
public class Main {
static class Task {
public int[] tn(int a){
int f[] = new int[11];
if(a==0) {
return new int[2];
}
int p = 1;
while(a>0){
int w = a%10;
f[p++] = w;
a/=10;
}
return Arrays.copyOf(f,p);
}
public int[] tt(String a){
int f[] = new int[2010];
int p = 1;
for(int i=a.length()-1;i>=0;--i) {
f[p++] = a.charAt(i)-'0';
}
return Arrays.copyOf(f, p);
}
static int rt = 0;
static int ch[][] ;
static int fa[];
static int id[];
static int mk[];
static int ct = 1;
static int cnt[];
static void insert(String s,int j,int num) {
int p = 0; // root
for (char c : s.toCharArray()) {
int d = c - 'A';
if (ch[p][d] == 0) {
ch[p][d] = ct++;
}
p = ch[p][d];
// mk[p]+= num;
}
mk[p] = 1;
id[p] = j;
}
static int q[] ;
static void build(){
int s = 0; int e = 0;
for(int i=0;i<26;++i) {
if(ch[0][i]>0) {
q[e++] = ch[0][i];
}
}
while(s<e){
int c = q[s++];
if(id[fa[c]]>0){
id[c] = id[fa[c]];
}
for(int j=0;j<26;++j){
if(ch[c][j]>0){
fa[ch[c][j]] = ch[fa[c]][j];
q[e++] = ch[c][j];
}else{
ch[c][j] = ch[fa[c]][j];
}
}
}
// for(int i=e-1;i>=0;--i){
// if(id[q[i]]!=-1){
// cnt[id[q[i]]] += mk[q[i]];
// }
// mk[fa[q[i]]] += mk[q[i]];
// }
}
static int search(String s){
int at = 0;
int cnt = 0;
for(char c:s.toCharArray()){
int to = c-'a';
to = ch[at][to];
int j = to;
while(j != 0) {
cnt += mk[to];
j = fa[j];
}
}
return cnt;
}
public void solve(int testNumber, InputReader in, PrintWriter out) {
int t = 1;
for(int i=0;i<t;++i){
int n = in.nextInt();
int m = in.nextInt();
rt = 0;
ct = 1;
cnt = new int[n];
String s[] = new String[n];
int tot = 0;
Map<String,Integer> mp = new HashMap<>();
Map<String,Integer> cf = new HashMap<>();
int ids = 0;
String ss[] = new String[n];
for(int j=0;j<n;++j){
s[j] = in.next();
if(mp.containsKey(s[j])){
cf.put(s[j],cf.get(s[j])+1);
} else {
ss[ids] = s[j];
mp.put(s[j],ids++);
tot += s[j].length();
cf.put(s[j],1);
}
}
q = new int[tot+1];
ch = new int[tot+1][26];
fa = new int[tot+1];
mk = new int[tot+1];
id = new int[tot+1];
Arrays.fill(id,-1);
for(int j=0;j<ids;++j){
insert(ss[j], j+1, cf.get(ss[j]));
}
build();
int at = 0;
long dp[][][] = new long[m+1][ct][2];
long mod = 10007;
dp[0][0][0] = 1;
for(int j=1;j<=m;++j){
for(int lst=0;lst<ct;++lst){
for(int k=0;k<26;++k){
int to = ch[lst][k];
if(id[to]>0){
dp[j][to][1] += dp[j-1][lst][0];
dp[j][to][1] %= mod;
dp[j][to][1] += dp[j-1][lst][1];
dp[j][to][1] %= mod;
}else{
dp[j][to][1] += dp[j-1][lst][1];
dp[j][to][1] %= mod;
dp[j][to][0] += dp[j-1][lst][0];
dp[j][to][0] %= mod;
}
}
}
}
long r = 0;
for(int lst=0;lst<ct;++lst){
r += dp[m][lst][1];
r %= mod;
}
out.print(r);
}
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, () -> solve(), "1", (1 << 30)).start();
// solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++14(g++5.4) 解法, 执行用时: 126ms, 内存消耗: 1000K, 提交时间: 2019-12-14 01:11:03
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 6e4;
const int MOD = 10007;
struct Node {
int ch[26];
int fail;
int val;
};
Node nodes[MAXN];
int sz;
void insert(string s) {
int cur = 0;
for (auto ch: s) {
int id = ch - 'A';
int &nxt = nodes[cur].ch[id];
if (nxt == 0) nxt = ++sz;
cur = nxt;
}
nodes[cur].val = true;
}
void build() {
queue<int> Q; Q.push(0);
while (!Q.empty()) {
auto s = Q.front(); Q.pop();
for (int i = 0; i < 26; i++) {
int &t = nodes[s].ch[i];
int f = nodes[s].fail;
if (t == 0) t = nodes[f].ch[i];
else {
while (f && !nodes[f].ch[i]) f = nodes[f].fail;
nodes[t].fail = !s?0: nodes[f].ch[i];
nodes[t].val |= nodes[nodes[t].fail].val;
Q.push(t);
}
}
}
}
int main() {
int N, M; cin >> N >> M;
while (N--) {
string s; cin >> s;
insert(s);
}
build();
vector<vector<int>> cur(2, vector<int>(sz+1));
cur[0][0] = 1;
while (M--) {
vector<vector<int>> nxt(2, vector<int>(sz+1));
for (int h = 0; h < 2; h++) {
for (int s = 0; s <= sz; s++) {
for (int i = 0; i < 26; i++) {
int t = nodes[s].ch[i];
if (nodes[t].val) nxt[1][t] = (nxt[1][t] + cur[h][s]) % MOD;
else nxt[h][t] = (nxt[h][t] + cur[h][s]) % MOD;
}
}
}
cur = nxt;
}
int tot = 0;
for (int s = 0; s <= sz; s++) {
tot = (tot + cur[1][s]) % MOD;
}
cout << tot << endl;
}
C++11(clang++ 3.9) 解法, 执行用时: 48ms, 内存消耗: 3304K, 提交时间: 2020-03-05 14:06:31
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 10007
using namespace std;
int n,m,sz=1,ans1,ans2=1;
int a[6001][27],point[6001],q[6001],f[101][60001];
char s[101];
bool danger[6001];
void ins()
{
int now=1,c;
for(int i=0;i<strlen(s);i++)
{
c=s[i]-'A'+1;
if(a[now][c]) now=a[now][c];
else now=a[now][c]=++sz;
}
danger[now]=1;
}
void acmach()
{
int t=0,w=1,now;
q[0]=1;point[1]=0;
while(t<w)
{
now=q[t++];
for(int i=1;i<=26;i++)
{
if(!a[now][i]) continue;
int k=point[now];
while(!a[k][i]) k=point[k];
point[a[now][i]]=a[k][i];
if(danger[a[k][i]])
danger[a[now][i]]=1;
q[w++]=a[now][i];
}
}
}
void dp(int x)
{
for(int i=1;i<=sz;i++)
{
if(danger[i]||!f[x-1][i]) continue;
for(int j=1;j<=26;j++)
{
int k=i;
while(!a[k][j]) k=point[k];
f[x][a[k][j]]=(f[x][a[k][j]]+f[x-1][i])%mod;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=26;i++) a[0][i]=1;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
ins();
}
acmach();
f[0][1]=1;
for(int i=1;i<=m;i++) dp(i);
for(int i=1;i<=m;i++)
ans2=(ans2*26)%mod;
for(int i=1;i<=sz;i++)
if(!danger[i]) ans1=(ans1+f[m][i])%mod;
printf("%d",(ans2-ans1+mod)%mod);
return 0;
}