求N个点中取偶数个点相连的种类数并取模

Question

现有N个点从1到N编号，每个点只可以与其余一个点相连或者不相连，即对于任意一个N最多有【N/2】取整对点相连，求N个点如何相连的种类数并取模。
要求输入N和m，输出种类数mol m 后的结果。
数据N<=10000000，2<=m<=10^13。
例如N分别等于2,3,4,5时种类数分别为2,4,10,26。

#include<stdio.h>
long long m;
int main()
{ 
  long long f(int x,int y);
  long long t,i,j,n,sum=1;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n/2;i++)
     {
     sum+=f(n,i)%m;
     }
  printf("%lld",sum%m);
return 0;
}
long long f(int x,int y)
{   
     long long i;
     if(y==1) 
     return x*(x-1)/2;
     else
     return (f(x,y-1)*(x-2*y+2)*(x-2*y+1))/(2*y);
}

用排列组合递归的思想写出了一个代码，但对于很大的N该代码运算会超时或答案错误，想找到取余或者运算的优化方法。

Answer 1

试一下我的代码

#include <stdio.h>

long long func(long long n, long long m)
{
    long long r1 = 1;
    long long r2 = 1;
    long long r = 0;

    for (long long i = 0; i < n; ++i) {
        r = (r2 * i % m + r1 % m) % m;
        r2 = r1;
        r1 = r;
    }

    return r;
    // if (n < 2) {
    //     return 1;
    // }
    // return func(n - 1) + (n - 1) * func(n - 2);
}

int main()
{
    long long n, m;

    scanf("%lld%lld", &n, &m);

    printf("%lld", func(n, m));
}

10000000 10000000000000
2767024144384