HDU 7105 Power Sum

发表于 | 分类于 | 评论数：

摘要

给出 $n\ (1\leq n\leq 10^6)$ ，求长度为 $K\ (1\leq K\leq n+2)$ 的数列 ${a_i}\ (a_i\in {-1, 1})$ 使得 $\sum_{i=1}^Ka_i\times i^2=n$

题面

题解

构造

注意到平方差 $(x+1)^2-x^2=2x+1$

两个平方差的差为 $(x+3)^2-(x+2)^2-(x+1)^2+x^2=4$

这意味着任意位置的串 1001 带来值 $4$

于是只需构造 $N\mod 4$ 的余数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//https://acm.dingbacode.com/showproblem.php?pid=7105
//20211014 nksbwen

#include <iostream>
#include <string>

using namespace std;

int T;
int N;

string Base[4]={"", "1", "0001", "01"};

int main(){
	
	scanf("%d", &T);
	
	while(T--){
		scanf("%d", &N);
		
		string Ans=Base[N&3];
		N-=N&3;
		while(N){
			Ans+="1001";
			N-=4;
		}
		
		printf("%llu\n", Ans.length());
		cout << Ans << endl;
	}
	
	
	return 0;
}