SRM382 div2 hard

難しかった。
まずある数列の
（偶数番目の要素の和）＝（奇数番目の要素の和）である集合をP
（前半の和）＝（後半の和）である集合をQとする

DP[i][j]をi個の要素を持ち和がjである数列の数だとする(並び替えは違うものとする)
するとn(P)＋n(Q)はDPで求められる。（＊１）

次にn(P∩Q)を求める
前半K個の和をhalf、その中で偶数番目のものの和をquarterとする
（＊２）

それでn(P)+n(Q)-n(P∩Q)を返す

#include <cstring>
#include <string>
#define MOD 999983  

typedef long long LL;
using namespace std;

class CharmingTicketsEasy
{
	public:

		LL DP[70][500];

		int count(int K, string good)
		{
			memset(DP,0,sizeof(DP));
			DP[0][0]=1;
			for(int i=0;i<K;i++)
				for(int j=0;j<460;j++)
					for(int k=0;k<(int)good.size();k++)
					{
						DP[i+1][j+good[k]-'0']+=DP[i][j];
						DP[i+1][j+good[k]-'0']%=MOD;
					}

			LL U=0;
			for(int i=0;i<460;i++)							//n(P)+n(Q)をUとしている
				U=(U+(DP[K][i]*DP[K][i])*2)%MOD;	//＊１

			LL P=0;
			for(int half=0;half<460;half++)
				for(int quarter=0;quarter<=half;quarter++)
				{
					LL a=DP[K-K/2][quarter]*DP[K/2][half-quarter];
					a%=MOD;					//Pはn(P∩Q)
					P=(P+a*a)%MOD;	//＊２
				}

			return ((U-P)%MOD+MOD)%MOD;
		}
};