Now Vasya is taking an exam in mathematics. In order to get a good mark, Vasya needs to guess the matrix that the teacher has constructed!
Vasya knows that the matrix consists of n rows and m columns. For each row, he knows the xor (bitwise excluding or) of the elements in this row. The sequence a1, a2, ..., an denotes the xor of elements in rows with indices 1, 2, ..., n, respectively. Similarly, for each column, he knows the xor of the elements in this column. The sequence b1, b2, ..., bm denotes the xor of elements in columns with indices 1, 2, ..., m, respectively.
Help Vasya! Find a matrix satisfying the given constraints or tell him that there is no suitable matrix.
Input
The first line contains two numbers n and m (2 ≤ n, m ≤ 100) — the dimensions of the matrix.
The second line contains n numbers a1, a2, ..., an (0 ≤ ai ≤ 109), where ai is the xor of all elements in row i.
The third line contains m numbers b1, b2, ..., bm (0 ≤ bi ≤ 109), where bi is the xor of all elements in column i.
Output
If there is no matrix satisfying the given constraints in the first line, output "NO".
Otherwise, on the first line output "YES", and then n rows of m numbers in each ci1, ci2, ... , cim (0 ≤ cij ≤ 2·109) — the description of the matrix.
If there are several suitable matrices, it is allowed to print any of them.
Examples
2 3
2 9
5 3 13
YES
3 4 5
6 7 8
3 3
1 7 6
2 15 12
NO
题意：
有一个n*m的矩阵，每一个方格中有一个数。
现在给你 两组数
第一组，有n 个数 每一个数i代表 第i行的所有数异或起来的数值。
第二组，有m 个数 每一个数j代表 第j列的所有数异或起来的数值。
问你是否存在一个矩阵，使之满足上面的条件，如果存在，请输出任意一个。
思路：
很好的一个构造题，
我们来看上图的情况，ai代表是列的异或值，bi代表是那一列的异或值。
那么
a1=x1^x4
a2=x2^x5
a3=x3^x6
b1=x1^x2^x3
b2=x4^x5^x6
a1^a2^a3=x1^x2^x3^x4^x5^x6
b1^b2=x1^x2^x3^x4^x5^x6
所以我们看数组a和数组b的分别异或起来的值是否相等，如果相等就存在答案，反而反之。
我们再来看如何构造出答案数组，
我们可以以一下的方式构造最为简单，
把最后一行赋值为a[i] ,最后一列赋值为b[j] ，其他全赋值为0（因为0异或任意值x等于x）
，然后最右下角的数x赋值为 a1^a2^a3....^a(m-1) ^ bn
根据异或的性质就可以推算出 这个x就既满足行又满足列的关系。
例如行上， x ^ (a1~a m-1 ) = bn ， 然后按照这个方法实现code就可以了，细节见代码。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define rt return #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} inline void getInt(int* p); const int maxn=1010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ ll a[maxn]; ll b[maxn]; ll ans[102][103]; int main() { //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin); //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout); ll n,m; cin>>n>>m; ll t1=0ll; ll t2=0ll; repd(i,1,n) { cin>>a[i]; t1^=a[i]; } repd(i,1,m) { cin>>b[i]; t2^=b[i]; } if(t1!=t2) { cout<<"NO"<<endl; }else { repd(i,1,n) { ans[i][m]^=a[i]; } repd(j,1,m) { ans[n][j]^=b[j]; } t2^=b[m]; t2^=a[n]; ans[n][m]=t2; cout<<"YES"<<endl; repd(i,1,n) { repd(j,1,m) { cout<<ans[i][j]<<" "; } cout<<endl; } } return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }
京公网安备 11010502036488号