链接
https://vjudge.net/problem/UVA-1358
题解
借助
k
m
p
kmp
kmp写出递推关系 然后用高斯消元去解 这题的答案貌似一定是整数（我也不知道为啥）
代码
#include <bits/stdc++.h>
#define cl(x) memset(x,0,sizeof(x))
using namespace std
;
typedef long long ll
;
struct matrix
{
ll n
, m
, a
[15][15];
ll
* operator[](ll index
){return a
[index
];}
void clear(){n
=m
=0;cl(a
);}
void gauss()
{
ll i
, j
, k
, r
;
for(i
=1;i
<=n
;i
++)
{
r
=i
;
for(j
=i
+1;j
<=n
;j
++)if(a
[j
][i
])r
=j
;
for(j
=1;j
<=n
+1;j
++)swap(a
[i
][j
],a
[r
][j
]);
for(j
=i
+1;j
<=n
;j
++)
{
while(a
[j
][i
])
{
ll
t(a
[i
][i
]/a
[j
][i
]), tmp
;
for(k
=i
;k
<=n
+1;k
++)
{
tmp
=a
[j
][k
];
a
[j
][k
]=a
[i
][k
]-t
*a
[j
][k
];
a
[i
][k
]=tmp
;
}
}
}
}
}
ll
getval(ll index
)
{
return a
[index
][n
+1]/a
[index
][index
];
}
void show()
{
ll i
, j
;
for(i
=1;i
<=n
;i
++)for(j
=1;j
<=m
;j
++)printf("%lld",a
[i
][j
]), putchar(j
==m
?10:32);
}
}mat
;
struct KMP
{
int n
, next
[15], t
[15];
void clear()
{
cl(next
), n
=0;
}
void build(int *r
, int len
)
{
int i
, j
=0;
n
=len
;
for(i
=1;i
<=len
;i
++)t
[i
]=r
[i
];
for(i
=2;i
<=len
;i
++)
{
for(;j
and t
[j
+1]!=t
[i
];j
=next
[j
]);
next
[i
] = t
[j
+1]==t
[i
]?++j
:0;
}
}
int move(int pos
, int x
)
{
for(;pos
and t
[pos
+1]!=x
;pos
=next
[pos
]);
return t
[pos
+1]==x
? pos
+1 : 0;
}
}kmp
;
int read(int x
=0)
{
int c
, f(1ll);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-48;
return f
*x
;
}
int main()
{
auto T
=read();
int kase(0);
while(T
--)
{
auto n
=read();
char s
[15];
int r
[15], i
, len
;
scanf("%s",s
+1);
len
=strlen(s
+1);
for(auto i
=1;i
<=len
;i
++)r
[i
]=s
[i
]-'A'+1;
r
[len
+1]=0;
kmp
.clear();
kmp
.build(r
,len
);
mat
.clear();
mat
.n
=len
+1, mat
.m
=len
+2;
for(i
=1;i
<len
;i
++)
{
mat
[i
][i
]=n
;
for(auto alpha
=1;alpha
<=n
;alpha
++)
{
auto to
=kmp
.move(i
,alpha
);
if(to
==0)to
=len
+1;
mat
[i
][to
]-=1;
}
mat
[i
][len
+2]=n
;
}
mat
[len
+1][len
+1]=n
;
for(auto alpha
=1;alpha
<=n
;alpha
++)
{
auto to
=kmp
.move(0,alpha
);
if(to
==0)to
=len
+1;
mat
[len
+1][to
]-=1;
}
mat
[len
+1][len
+2]=n
;
mat
[len
][len
]=1;
mat
[len
][len
+2]=0;
mat
.gauss();
kase
++;
printf("Case %d:\n%lld\n",kase
,mat
.getval(len
+1) );
if(T
)putchar(10);
}
return 0;
}
