C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 596K, 提交时间: 2020-04-01 21:11:35

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct long_int
{
	int num[300],cnt;
	void operator = (int y)
	{
		num[1]=y;
		cnt=1;
	}
	int &operator [](int x)
	{
		return num[x];
	}
 }S[20];
void operator *=(long_int &x,long_int &y)
{
	long_int z=S[19];
	int i,j;
	for(i=1;i<=x.cnt;i++)
	for(j=1;j<=y.cnt;j++)
	{
		z[i+j-1]+=x[i]*y[j];
		z[i+j]+=z[i+j-1]/10000;
		z[i+j-1]%=10000;
	}
	z.cnt=x.cnt+y.cnt;
	if(!z[z.cnt])
	--z.cnt;
	x=z;
}
void operator ++ (long_int &x)
{
	int i=1;
	x[1]++;
	while(x[i]==10000)
	x[i]=0,x[++i]++;
}
long_int operator - (long_int &x,long_int &y)
{
	long_int z=S[19];
	int i;
	for(i=1;i<=x.cnt;i++)
	{
		z[i]+=x[i]-y[i];
		if(z[i]<0)
		z[i]+=10000,z[i+1]--;
		if(z[i])
		z.cnt=i;
	}
	return z;
}
long_int operator ^(long_int x,int y)
{
	long_int z=S[19];
	z=1;
	while(y)
	{
		if(y&1) z*=x;
		x*=x;
		y>>=1;
	}
	return z;
}
ostream &operator <<(ostream &os,long_int x)
{
	int i;
	os<<x[x.cnt];
	for(i=x.cnt-1;i;i--)
	os<<setfill('0')<<setw(4)<<x[i];
	return os;
}
int n,d;
int main()
{
	int i;
	cin>>n>>d;
	if(!d)
	{
		puts("1");
		return 0;
	}
	S[0]=1;
	for(i=1;i<=d;i++)
	S[i]=S[i-1]^n,++S[i];
	cout<<S[d]-S[d-1]<<endl;
}