#HDR003C. 「MCOI-06」Existence of Truth

「MCOI-06」Existence of Truth

题目描述

可能存在一个非负整数数序列 a1,a2,,ana_1,a_2,\dots,a_n 使得 0ai<109+70\le a_i < 10^9+7

给定 x1,x2,,xnx_1,x_2,\dots,x_ny1,y2,,yny_1,y_2,\dots,y_nz1,z2,,znz_1,z_2,\dots,z_n,已知对于 1in1\le i\le n 满足:

xi(j=1iaj)+yi(j=inaj)zi(mod109+7)x_i\left(\sum_{j=1}^ia_j\right)+y_i\left(\sum_{j=i}^na_j\right)\equiv z_i\pmod{10^9+7}

a1,a2,,ana_1,a_2,\dots,a_n

输入格式

本题有多组数据。

第一行一个正整数 TT,表示表示数据的组数。对于每一组数据:

第一行一个正整数 nn

接下来 nn 行,每行三个正整数 xi,yi,zix_i,y_i,z_i

输出格式

对于每一组数据,依次输出:

第一行一个非负整数 kk,为合法解数量。

如果 k=1k=1,第二行输出 nn 个正整数,依次为 a1,a2,,ana_1,a_2,\dots,a_n

2
3
3 1 9
2 2 16
1 3 15
6
3 6 246
5 7 283
2 7 179
4 6 214
8 7 337
3 5 151
1
1 2 3
1
8 8 0 6 7 8

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(10 pts):n=1n=1
  • Subtask 2(19 pts):n100\sum n\le100
  • Subtask 3(19 pts):xi=yi=1x_i=y_i=1
  • Subtask 4(22 pts):保证有唯一解。
  • Subtask 5(30 pts):无特殊限制。

对于所有数据:

  • 1n,n2×1051\le n,\sum n\le 2\times10^5
  • 1xi,yi<109+71\le x_i,y_i < 10^9+7
  • 0zi<109+70\le z_i < 10^9+7