函数 [计数]

感谢 JR 赞助

$SOLUTION$SOLUTION

设 $F\left(x\right)=y$F(x)=y, 沿着 $F\left[F\right(x\left)\right]=-x$F[F(x)]=−x 这个规则推

$F\left(x\right)=yX$F(x)=y                             X
$\downarrow$         ↓
$F\left(y\right)=F\left[F\right(x\left)\right]=-x$F(y)=F[F(x)]=−x
$\downarrow$                   ↓
$F(-x)=F\left[F\right(y\left)\right]=-y$F(−x)=F[F(y)]=−y
$\downarrow$                   ↓
$F(-y)=F\left[F\right(-x\left)\right]=x$F(−y)=F[F(−x)]=x
$\downarrow$                   ↓
$F\left(x\right)=F\left[F\right(-y\left)\right]=yY$F(x)=F[F(−y)]=y        Y

会发现 $X$X式 又等价于 $Y$Y式,
得出结论: 对两个正整数 $x,y$x,y, $F\left(x\right)=\pm y$F(x)=± y, 只会影响到 $F\left(x\right),F\left(y\right),F(-x),F(-y)$F(x),F(y),F(−x),F(−y)四个函数的值.

不考虑负数的存在, 原问题转换为
求 $1,2,3,..,R$1,2,3,..,R 序列中两两配对的方案数,
$F\left(x\right)=\pm y$F(x)=± y 是两种不同的方案, 即一次配对有两种不同的选择,
$\therefore Ans=2^{R/2}\ast (N-1)\ast (N-3)...\ast 1$∴Ans=2R/2∗(N−1)∗(N−3)...∗1

$CODE$CODE

#include<bits/stdc++.h>
#define reg register

const int maxn = 10000007;

int L;
int R;
int Ans;

const int mod = 666623333;

int KSM(int a, int b){
        int s = 1;
        while(b){
                if(b & 1) s = 1ll*s*a % mod;
                a = 1ll*a*a % mod;
                b >>= 1;
        }
        return s;
}

int main(){
        scanf("%d%d", &L, &R); 
        if(L != -R) printf("0\n"); 
        else if((L&1) || (R&1)) printf("0\n"); 
        else{ 
                Ans = KSM(2, R/2); 
                for(reg int i = 3; i <= R; i += 2){ 
                        Ans = 1ll*Ans*i % mod; 
                } 
                printf("%d\n", Ans);
        }
        return 0;
}