プロジェクトオイラー問201 - sinapusu2002 @ ウィキ

https://projecteuler.net/problem=201
1^2,2^2,,,100^2
から重複なく５０個選んでその和をとるとき、１通りの表し方しかできない数の和を答えよ。

0、1、２通り以上の表し方ができるの３パターンで後は漸化式で終わりです。

#include<stdio.h>
#include<iostream>
#include<math.h>

const __int64 MASK=(__int64)pow(2,50)-1;
const int LIMIT=340000;
__int64 cs1[LIMIT]={0};
__int64 cs2[LIMIT]={0};

int main(){
	__int64 ans=0;
	for(int i=1;i<=100;i++){
		int n=i*i;
		for(int j=LIMIT-1-n;j-n>0;j--){
			__int64 p1=cs1[j];
			__int64 p2=(cs1[j-n]<<1)&MASK;
			cs1[j]=(p1|p2);
			__int64 p3=(p1&p2);
			cs2[j]=(cs2[j]|p3)|((cs2[j-n]<<1)&MASK);
		}
		cs1[n]=(cs1[n]|1);
	}
	for(int i=1;i<LIMIT;i++){
		__int64 p1=(cs1[i]>>49)&1;
		__int64 p2=(cs2[i]>>49)&1;
		if(p1==1&&p2==0)ans+=i;
	}
	std::cout<<ans<<"\n";
}