AOJ 2164: Revenge of the Round Table

まあケースあたりO(N^2)くらいのDPをするだけ。
ケースがたくさんあるから最初に全部前計算をtotal O(N^3)未満でやるのかなと思ったら、ケース数が全然なかった。(このせいで無駄に時間を消費した)
テストケース数に強く依存する計算量の問題はケース数とかをちゃんと書くかmultiple testcaseをやめるべきだと思う。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long mod=1000003;
long long inv[1000003];
long long dp[1100][1100];
long long sum[1100][2];
long long dp2[1100][2];
int gcd(int a,int b){
	while(a){
		b%=a;int c=a;a=b;b=c;
	}
	return b;
}
int num[1100];
long long calc(int a,int b){
	if(~dp[a][b])return dp[a][b];
	long long ret=0;
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++)sum[j][0]=sum[j][1]=dp2[j][0]=dp2[j][1]=0;
		dp2[i][0]=1;sum[i][0]=1;
		for(int j=i+1;j<=b;j++){
			dp2[j][1]=(sum[j-1][0]+mod-sum[max(0,j-1-a)][0])%mod;
			if(j==b)dp2[j][0]=(dp2[j][0]+sum[j-1][1]+mod-sum[max(0,j-1-(a-i))][1])%mod;
			else dp2[j][0]=(dp2[j][0]+sum[j-1][1]+mod-sum[max(0,j-1-a)][1])%mod;
			sum[j][0]=(sum[j-1][0]+dp2[j][0])%mod;
			sum[j][1]=(sum[j-1][1]+dp2[j][1])%mod;
		}
		ret=(ret+dp2[b][0]+dp2[b][1])%mod;
	}
	ret=ret*2%mod;
	return dp[a][b]=ret;
}
int main(){
	int a,b;
	inv[1]=1;
	for(int i=2;i<mod;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<1100;i++){
		int c=i;
		int v=2;
		while(c>1){
			if(c%v==0){
				c/=v;num[i]++;
			}else v++;
		}
	}
	for(int i=0;i<1100;i++)for(int j=0;j<1100;j++)dp[i][j]=-1;
	while(scanf("%d%d",&a,&b),a){
		int ad=0;
		if(b>=a)ad=2;
		if(b>=a)b=a-1;
		long long ret=0;
		for(int i=1;i<=a;i++){
			int t=gcd(i,a);
			ret=(ret+calc(min(t-1,b),t))%mod;
		}
		//printf("%lld\n",ret);
		ret=ret*inv[a]%mod;
		printf("%lld\n",(ret+ad)%mod);
	}
}