C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 1776K, 提交时间: 2019-03-16 13:11:40

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=1e9;
struct Big
{
	ll S[12345],T,cur;
	void Input()
	{
		string s;cin>>s;ll i,t,l=s.length();
		for(i=0;i<l;i++)
		{
			t=(l-i-1)/9;S[t]=S[t]*10+s[i]-48;
			T=T*10+s[i]-48;T%=3388;
		}
		cur=(l-1)/9;while(cur>0&&S[cur]==0)cur--;
	}
	void Output()
	{
		printf("%lld",S[cur]);
		ll i,k;
		for(i=cur-1;i>=0;i--)
		{
			k=mod/10;
			while(k>S[i])putchar('0'),k/=10;
			if(k)printf("%lld",S[i]);
		}
	}
	void add(ll k)
	{
		S[0]+=k;ll i=0;
		while(S[i]>=mod)S[i+1]+=S[i]/mod,S[i++]%=mod;
		if(S[cur+1])cur++;
	}
	void ADD(const Big& o)
	{
		ll i,r=max(o.cur,cur);
		for(i=0;i<=r;i++)
		{
			S[i]+=o.S[i];
			if(S[i]>=mod)S[i+1]+=S[i]/mod,S[i]%=mod;
		}
		cur=r+5;while(cur>0&&S[cur]==0)cur--;
	}
	void Multiply(const Big& o,Big& E)
	{
		ll i,j;memset(&E,0,sizeof(E));
		for(i=0;i<=cur;i++)
		for(j=0;j<=o.cur;j++)
		{
			E.S[i+j]+=S[i]*o.S[j];
			if(E.S[i+j]>=mod)
			{
				E.S[i+j+1]+=E.S[i+j]/mod;
				E.S[i+j]%=mod;
			}
		}
		E.cur=cur+o.cur+5;
		while(E.cur>0&&E.S[E.cur]==0)E.cur--;
	}
	void Divide(ll k)
	{
		for(ll i=cur;i>0;i--)
		{
			S[i-1]+=S[i]%k*mod;S[i]/=k;
			if(S[cur]==0)cur--;
		}
		S[0]/=k;
	}
};
Big N,M,C[12],t1,t2,t3,P[12],Ans;
ll a,i,j,k,K;
int main()
{
	N.Input();P[1].Input();M.Input();
	K=N.T-M.T;if(K<0)K+=3388;
	a=1;for(i=1;i<=M.T;i++)a=(1234*a+5678)%3389;
	Ans.add(a);C[0].S[0]=1;
	for(k=1;k<=K;k++)
	{
		M.add(1);
		C[k-1].Multiply(M,C[k]);
		C[k].Divide(k);
		a=(a*1234+5678)%3389;
		P[k].Multiply(P[1],P[k+1]);
		t2.S[0]=a;
		C[k].Multiply(t2,t1);
		P[k].Multiply(t1,t3);
		Ans.ADD(t3);
	}
	Ans.Output();
}