思路
由于起点和终点都是1，可以看作1经过n-1次运算重新得到1。那么设x+y+z=n-1;有(-2)^x*(1/2)^y*(1)^z=1；容易想到x为偶数，而且x=y。所以枚举x，y可能的结果，然后就成了排列问题。预处理阶乘及其逆元，可以O(1)求解组合数，总的复杂度O(n)；
代码#include<bits/stdc++.h>usingnamespacestd;#definemaxn1005#definemaxm1000006#definelllonglongint#defineINF0x3f3f3f3f#defineinc(i,l,r)for(inti=l;i<=r;i++)#definedec(i,r,l)for(inti=r;i>=l;i--)#definemem(a)memset(a,0,sizeof(a))#definesqr(x)(x*x)#defineinf(ll)2e18+1#definemod1000000007intread(){intx=0,f=1;charch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();returnf*x;}intn;llf[maxn],g[maxn];llfast(llx,lly){llres=1ll;while(y){if(y&1)res=res*x%mod;x=x*x%mod;y>>=1;}returnres;}voidinit(){f[0]=g[0]=1;inc(i,1,maxn-1)f[i]=f[i-1]*i%mod;g[maxn-1]=fast(f[maxn-1],mod-2);dec(i,maxn-2,1)g[i]=g[i+1]*(i+1)%mod;}intmain(){printf("%lld\n",1ll*2500*fast(10000,mod-2)%mod);init();n=read();llans=0;inc(i,0,n-1){intx=i*2,y=i*2,z=n-1-x-y;if(z<0)break;ans=(ans+f[n-1]*g[x]%mod*g[y]%mod*g[z]%mod)%mod;}printf("%lld\n",ans);return0;}
