您的题目中图片不是按照vijos要求的格式上传的.
请通过"我的文件"将图片上传到vijos, 然后修改题目描述中的图片链接.

图片会存储在cdn中, 例如P1683中的那幅图地就是vijos://fs/066e2e2025df9b7bc5d4ba5ed78c1db01581da22.
请通过代码![图片](vijos://fs/066e2e2025df9b7bc5d4ba5ed78c1db01581da22 )插入图片到题目中.

之后若无误我会把这三道题目插入到大题库中.
感谢您对vijos的支持.

加题的话请联系 @doc ~

我顶~~

@twd2
建议将三题加入Vijos官方题库

题目三：神探夏洛克之致命游戏3
题解：
Ans=n^(n-2)
证明点这里
提供标程（别忘了写快速乘）（P.S有兴趣写高精度也行）

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL Quick_Mul(LL a,LL b,LL mod) {
LL ans=0;
while(b>0) {
if(b&1)ans=(ans+a)%mod;
b>>=1;
a=(a+a)%mod;
}
return ans;
}
LL Quick_Pow(LL a,LL b,LL mod) {
LL ans=1;
while(b>0) {
if(b&1)ans=Quick_Mul(ans,a,mod);
b>>=1;
a=Quick_Mul(a,a,mod);
}
return ans;
}
LL n,mod;
int main() {
n=Get_Int();
mod=Get_Int();
printf("%lld\n",Quick_Pow(n,n-2,mod));
return 0;
}

题目二：神探夏洛克之致命游戏1
题解点这里

题目一：神探夏洛克之致命游戏2
题解：
来自KEKE的题解
广义斐波那契数列 F[x]=F[x-1]+F[x-2] 可以写成 F[x]=a*F[1]+b*F[2] 的形式
写一个暴力程序算一下a和b

int a=0,b=0;
void F(int n){
if(n==1)a++;
else if(n==2)b++;
else F(n-1),F(n-2);
}

F[3]=1*F[1]+1*F[2]
F[4]=1*F[1]+2*F[2]
F[5]=2*F[1]+3*F[2]
F[6]=3*F[1]+5*F[2]
发现a,b是正常斐波那契数列的相邻两项。
问题就变成了拓展欧几里得解决不定方程的问题。
从第10项开始计算裴波那契数列直到能够求出方程的正整数解。
如果当前的数列的项大于了n此题无解，不过题目似乎所有数据都有解。
由于裴波那契数列是指数增加的，所以算法时间是 O(log^2(n)) 的。
即使数据达到 10^18 也可以秒出答案，没有精度影响。
代码参考:

#include<cstdio>
using namespace std;

//暴力开 long long
typedef int int_;
#define int long long

//拓展欧几里得计算 a*x+b*y==gcd(a,b) 的某一个解
void exgcd(int a,int b,int &d,int &x,int &y){
if(b==0){d=a;x=1;y=0;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}

//解不定方程 a*x+b*y==c 求出对x的最小非负整数解
//无解返回 -1
int solve(int a,int b,int c){
int d,x,y;
exgcd(a,b,d,x,y);
if(c%d)return -1;
x*=(c/d);b/=d;
return (x%b+b)%b;
}

int feb[1005];

int_ main(){
int N;scanf("%lld",&N);
//递推求出到N的斐波那契数列
feb[0]=0;feb[1]=1;
for(int k=2;;k++){
feb[k]=feb[k-1]+feb[k-2];
if(feb[k]>N)break;
}
//从第10项开始枚举求解
for(int k=10;feb[k]<=N;k++){
int x=solve(feb[k-1],feb[k],N);
if(x!=-1){
int y=(N-feb[k-1]*x)/feb[k];
if(y>=0){
int ans=feb[k]*x+feb[k+1]*y;
printf("%lld\n",ans);
break;
}
}
}
return 0;
}

官方题解
作为我出的题目呢，数据保证了不超过30000，因此可以使用广义斐波拉契的发展趋势来做。
为什么数据超过30000不能做了呢？因为计算机精度有限，否则是可以照样做下去的。
几乎所有的广义斐波拉契数列（全为正整数）两项之商会无限趋于(根号5+1)/2，这也是黄金比例。
因此可以用这个方法来做，当然黄金比例的值要取大一点。
时间复杂度O(1)
当然因为数据不大，大家也可以用楼上ZKX的方法做，更暴力，更准确。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const long long Get_Int() {
    long long num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
const long double tmp=(1+sqrt(5))/2;
long long n;
int main() {
    n=Get_Int();
    printf("%lld\n",(long long)(tmp*n+0.5));
    return 0;
}

比赛结果

排名 用户 解决 时间 #1 #2 #3
1 q234rty 3 172380.0 已通过 (85717.0) 已通过 (81809.0) 已通过 (4854.0)
2 xh2015 3 290895.0 已通过 (108594.0) 已通过 (87560.0) 已通过 (94741.0)
3 LCF 2 37519.0 - 已通过 (18905.0) 已通过 (18614.0)
4 Fop_zz 2 178440.0 - 已通过 (89428.0) 已通过 (89012.0)
5 这题男不男 2 405091.0 - 已通过 (194514.0) 已通过 (210577.0)
6 yiliang 1 32130.0 - - 已通过 (32130.0)
7 doc 1 37767.0 - - 已通过 (37767.0)

将在比赛后提供题解与标程，部分题目有多种解法，也希望大家提出新的思路，谢谢！

orz

赞一个 Orz

666

顶 orz