{"problem":{"name":"[中山市赛 2023] 组合数问题","description":{"content":"众所周知，骐度空间·莫羯座·十一月的萧彰同学擅长计算，尤其擅长计算组合数。 定义组合数 $\\binom{i}{j}=\\begin{cases}\\frac{i!}{j!(i-j)!}&i\\ge j\\ge 0\\\\0&其他情况\\end{cases}$，可以证明对于任意 $i,j$，$\\binom{i}{j}$ 总是整数。 这天，骐度空间·莫羯座·十一月的萧彰遇到了一道难题。有一个 $n\\times ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4338"},"statements":[{"statement_type":"Markdown","content":"众所周知，骐度空间·莫羯座·十一月的萧彰同学擅长计算，尤其擅长计算组合数。\n\n定义组合数 $\\binom{i}{j}=\\begin{cases}\\frac{i!}{j!(i-j)!}&i\\ge j\\ge 0\\\\0&其他情况\\end{cases}$，可以证明对于任意 $i,j$，$\\binom{i}{j}$ 总是整数。\n\n这天，骐度空间·莫羯座·十一月的萧彰遇到了一道难题。有一个 $n\\times n$ 的矩阵，$(i,j)$ 表示第 $i$ 行第 $j$ 列，有 $Q$ 次操作，每次操作给定子矩阵的两个端点（分别为 $(x1,y1)$ 和 $(x2,y2)$），对于所有原矩阵中的所有位置 $(x,y)$ 满足 $x1\\le x\\le x2$，$y1\\le y\\le y2$ 加上 $\\binom{x-x1}{y-y1}$。\n\n骐度空间·莫羯座·十一月的萧彰凭借超强的能力在 $0.0001s$ 内算出了答案，但他想考考你，顺便帮忙验证一下。\n\n骐度空间·莫羯座·十一月的萧彰想知道最后的矩阵长什么样，由于数很大，为了方便，每个位置的值都要对 $10^9 + 7$ 取模。\n\n然而输出量很大，骐度空间·莫羯座·十一月的萧彰无法快速比较这是否是正确答案，所以你只需要输出每一行的异或和和每一列的异或和即可。\n\n骐度空间·莫羯座·十一月的萧彰担心你不知道什么是异或运算，所以他直接给你的输出答案的模板：\n\n```cpp\nint ans[5010][5010];//假设这是最终的答案矩阵\nvoid print(){\n    for(int i=1;i<=n;i++){\n        int s=0;\n        for(int j=1;j<=n;j++) s^=ans[i][j];\n        printf(\"%d \",s);\n    }\n    printf(\"\\n\");\n    for(int i=1;i<=n;i++){\n        int s=0;\n        for(int j=1;j<=n;j++) s^=ans[j][i];\n        printf(\"%d \",s);\n    }\n}\n\n```\n\n## Input\n\n第一行两个正整数 $n$，$Q$。\n\n接下来 $Q$ 行，每行四个正整数 $x1, y1, x2, y2$，表示每次操作的子矩阵的两个端点。\n\n## Output\n\n第一行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 行的异或和。\n\n第二行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 列的异或和。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n最终的矩阵如下：\n\n```\n1 0 1\n1 1 1\n1 2 1\n```\n\n### 样例解释 2\n\n最终的矩阵如下：\n\n```\n1 1 0 0 0\n1 3 1 0 0\n1 4 4 1 0\n0 2 5 4 1\n0 2 7 9 4\n```\n\n### 数据范围\n\n对于 $10\\%$ 的数据，满足 $1 \\le n, Q \\le 10$。\n\n对于 $30\\%$ 的数据，满足 $1 \\le n, Q \\le 100$。\n\n对于 $40\\%$ 的数据，满足 $1 \\le n, Q \\le 500$。\n\n对于另外 $20\\%$ 的数据，满足所有操作的 $x2, y2$ 均等于 $n$。\n\n对于 $100\\%$ 的数据，满足 $1 \\le n, Q \\le 5000$。\n\n对于所有数据 $1 \\le x1 \\le x2 \\le n, 1 \\le y1 \\le y2 \\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4338","tags":["数学","2023","广东","前缀和","差分","科创活动","小学活动"],"sample_group":[["3 2\n1 1 3 2\n1 3 3 3\n","0 1 2\n1 3 1\n"],["5 3\n1 1 3 3\n2 2 5 4\n1 2 5 5\n","0 3 0 2 8\n1 6 7 12 5\n"],["10 9\n1 2 9 8\n2 4 3 6\n7 5 9 10\n1 2 10 9\n1 1 10 10\n2 5 6 8\n1 4 4 10\n1 3 9 10\n1 9 9 10\n","2 0 1 10 5 1 66 9 238 246\n0 0 44 84 3 81 66 40 0 30\n"]],"created_at":"2026-03-03 11:09:25"}}