这道题目刚出来的时候（大概是十二月二十七八日左右）觉得特别水，花了一点时间做了出来，谁知道最后还是被卡掉了……我的AC率啊！！！

 

于是稍稍推了一下递推式。

点动成线，所以一条线有两个点，线动成面，所以一个面有四条线，面的两边各有一条线，而两侧由于点的运动，又多了两条线。

面动成体，正对着的有两个面了，四周由于四条边在动，形成了四个新的面……

这样下去，一个k(k>0)维超正方体是由k*2个k-1维超正方体组成的。

还有一个规律，对于一个k维超正方体来说，k维的超正方体有1个，k-1维的超正方体有k*2个。

但是k-2维的超正方体并非k*2*(k-1)*2个，因为每两个k-1维超正方体之间都有2个k-2维的超正方体相交，所以要除以2，相对应的，k-3维超正方体=k-2维超正方体的数目*(k-2)*2/3……

但是，这道题最主要的问题是取模，有除法，所以需要求逆元，但是，用exgcd求逆元是O(log n)的，不过，Claris向我提供了一份O(n)求出所有逆元的代码，到目前为止，我还没有搞清楚这段代码的原理TAT

我怕这道题目变成权限题，于是马上就提交了这题，结果，有人加强了一下数据，把大多数人都卡掉了，于是我整个人就顿时不好了。

原来，还有一种神奇的情况就是，维数是模数的倍数，那么就不能求逆元了，我立马就束手无策了，好在Claris提供了帮助，对于一个数x，如果[tex]x=p*mod^k[/tex]，那么我们就不用管mod，将其逆元当作是p的逆元，递推的时候，再计算一下，当前的答案是否为mod的倍数，如果是mod的倍数的话，那么答案就是0，否则答案就是我们求出来的值。另外，如果模的数是2的话，发现答案永远是1，可以特判加速。

具体的可以看一下代码。

PS：这种时候，递推式算好像比通项公式要快。

 

UPD：关于线性递推求逆元的证明

    对于一个数i，其逆元inv[i]满足i*inv[i]%P=1

    设P=i*j+k，则j=P/i,k=P%i

    所以i=(P-k)/j%P=-k/j

    那么，inv[i]=1/i=-j/k=-j*inv[k]

    证毕

 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10001000;
int n,x,num;
ll t,last,ans=1,mod;
int r[N],a[N];
char c[N];
int main() {
    int i;
    scanf("%d%lld",&n,&mod);
    if (mod==2) return puts("1"),0;
    for(r[1]=a[1]=1,i=2;i<=n;i++) if (i%mod==0) {
        x=i;
        while (x%mod==0) {
            c[i]++;
            x/=mod;
        } r[i]=r[a[i]=x];
    } else {
        a[i]=i;
        if (i>=mod) r[i]=r[i%mod];
        else {
            r[i]=-(ll)r[mod%i]*(mod/i)%mod;
            while (r[i]<0) r[i]+=mod;
        }
    }
    for (last=i=1;i<=n;i++) {
        last=(((last*a[n-i+1]%mod)<<1)%mod)*r[i]%mod;
        num+=c[n-i+1]-c[i];
        if (!num) ans^=last;
    } cout<<ans<<endl;
    return 0;
}