题解：

当奇数

发现答案就是C（n,1）^2+C(n,3)^2+。。。C(n,n)^2

倒序相加，发现就是C（2n,n） 所以答案就是C(2n,n)/2

当偶数

好像并不会证

打表出来可以得到

2.当n为偶数且为4的倍数时，答案为C(2n,n)+C(n,n/2)/2

3.当n为偶数且不为4的倍数时，答案为C(2n,n)-C(n,n/2)/2

另外Claris告诉我在p较小时可以数位dp来求

先用lucas定理 C(n,m)=C(n%p,m%p)*C(n/p,m/p)

然后我们就可以把n表示成p进制

答案就是m在p进制下和对应n求C的乘积

然后我们可以数位dp这个东西

 

#include 
     
      using namespace std;#define ll long long#define rint register ll#define IL inline#define rep(i,h,t) for (rint i=h;i<=t;i++)#define dep(i,t,h) for (rint i=t;i>=h;i--)const ll p=1000003;const ll mo=1000003;const ll INF=1e18;const ll N=2e6;ll n,cnt=0,a[50],jc1[N],jc2[N],f[N][2][2];void gcd(ll x,ll y,ll &a,ll &b){  if (y==0)  {    a=1; b=0; return;  }  gcd(y,x%y,b,a);  b-=a*(x/y);}ll C(ll x,ll y){  if (x
      
       p) x-=p;}int main(){  cin>>n;  while (n) a[++cnt]=n%p,n/=p;  jc1[0]=jc2[0]=1;  rep(i,1,p)  {     jc1[i]=(jc1[i-1]*i)%p;    jc1[i]=(jc1[i]+p)%p;    ll x,y;    gcd(i,p,x,y);    jc2[i]=(jc2[i-1]*x)%p;    jc2[i]=(jc2[i]+p)%p;  }  f[cnt+1][0][0]=1;  dep(j,cnt,1)  {    ll tmp1j=0,tmp1o=0;    rep(i,0,a[j]-1)    {      ll kk=C(a[j],i);      kk=(kk*kk)%mo;      if (i%2)        jf(tmp1j,kk);      else jf(tmp1o,kk);    }    f[j][0][1]=(f[j+1][0][0]*tmp1o%mo+f[j+1][1][0]*tmp1j%mo)%mo;    f[j][1][1]=(f[j+1][0][0]*tmp1j%mo+f[j+1][1][0]*tmp1o%mo)%mo;    if (a[j]%2) jf(tmp1j,1); else jf(tmp1o,1);    f[j][0][1]+=(f[j+1][0][1]*tmp1o%mo+f[j+1][1][1]*tmp1j%mo)%mo;    f[j][1][1]+=(f[j+1][0][1]*tmp1j%mo+f[j+1][1][1]*tmp1o%mo)%mo;    if (f[j+1][1][0]) f[j][(1+a[j])%2][0]=1;    else f[j][a[j]%2][0]=1;  }  ll ans=(f[1][0][1]+f[1][0][0])%mo;  cout<
       
        <