简单地想，假设已知f（n-1) (n-1支牙刷的错排方案），那么对于其中任意一种方案，将其中n-1个元素任意一个与第n个交换，可得（n-1)f(n-1)种方案；
假设已知f(n-2),则n-1支牙刷必有一支（可以是任意一只）放在了原位置上，将其与第n支交换即可。共（n-1）f(n-1)种方案。
易知对f(n-3).....(f(1)不存在使f（n）成立的方案。
故f(n)=(n-1)(f(n-1)+f(n-2).

二分快速幂即可，基础代码程序。还有终于搞明白了一点，原来在评测页面刷新会导致程序重测，唉，悲催

对不起党。。。。

n<=10^4 Ai<=10^9 那S不应该小于10^13么。。。

@(⊙o⊙)… 不必这样贴，有点不美观，选中“允许查看你提交的代码”别人就可以看了

骑士游历问题

这题目略坑啊，竟然会有只有一个格子的测试数据。。。。这个时候是站着不动，只能特判了，否则过不去。
排除坑爹数据不谈，本题的思路是DP，类似于数字三角形，将动态的过程转化成静态的序列，之后倒序找最佳方案即可。输出可能需要费点心思。

program spy(input,output);
var
a,b:array['A'..'Z'] of char;
st1,st2,st3:string;
i,j,n:integer;
ch:char;
procedure work;
begin
writeln('Failed');
close(input);close(output);
halt;
end;
begin
assign(input,'spy.in');assign(output,'spy.out');
reset(input);rewrite(output);
readln;readln;readln;
n:=length;
for ch:='A' to 'Z' do
begin
a[ch]:='#';
b[ch]:='#';
end;
for i:=1 to n do
if ((a[st1[i]]='#') and (b[st2[i]]='#')) or (a[st1[i]]=st2[i]) then
begin
a[st1[i]]:=st2[i];
b[st2[i]]:='@';
end
else work;
for ch:='A' to 'Z' do
if b[ch]='#' then work;
for i:=1 to length do
write(a[st3[i]]);
writeln;
close(input);close(output);
end.

@常可神牛 不用像这样贴代码，这样太影响市容……把“允许查看你提交的代码”选上就行了

最后一个点答案-1，如果从s到t搜会超时TAT，但是从t到s搜就无压力了~

好奇妙的一道（小学奥数）题……

第九组数据有误。可以在数据中找到这样的两条边：(26,1)->(72,159)和(24,2)->(157,13)，显然它们相交，因此答案应为"NOFENCE"。事实上，这组数据的格式也有问题，看上去似乎是一个n=100的数据的一部分和一个n=199的数据拼接而成。
各位自行cheat。
if(n==100){cout<<"4\n45 81 43 188\n43 188 196 112\n196 112 199 -1\n199 -1 0 0\n";return 0;}

这题竟然没有数据，坑爹啊，害的我白交了一次

这是我的程序：

program P1778;

var

m,n:ansistring;

x:char;

i,j,k,l,c:integer;

begin

assign(input,'vigenere.in');

reset(input);

assign(output,'vigenere.out');

rewrite(output);

readln(m);

readln(n);

for i:=1 to length(m) do

m[i]:=lowercase(m[i]);

c:=length(m);

for i:=1 to 10 do

m:=m+m;

for i:=1 to length(n) do

begin

case n[i] of

'A'..'Z':

for x:='A' to 'Z' do

begin

j:=ord(m[i])-65;

k:=ord(x)-97;

l:=(k+j) mod 26+65;

if chr(l)=n[i] then begin write(x); break; end;

end;

'a'..'z':for x:='a' to 'z' do

begin

j:=ord(m[i])-97;

k:=ord(x)-97;

l:=(k+j) mod 26+97;

if chr(l)=n[i] then begin write(x); break; end;

end;

end;

end;

end.

其他Oj都能过啊！
http://wikioi.com/code/317292/
https://www.vijos.org/records/511240174e4112280f14c390
https://www.tyvj.cn/Record_Show.aspx?id=1068935

就是那两个函数问题，大家以后不要用啊，会全部超时的

不懂啊

单调栈~~单调栈~~O(n)

它说我超时！！其他oj能过啊……难道不能用upcase和lowercase？

谁能告诉我他刷了多少次！！！

直接粘代码果然是掉人品的事。。C、M和F、C 0和-1 囧