#include<bits/stdc++.h> usingnamespace std; #define ll long long constint INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; constint N = 3e5 + 10; int T; int a[400][400]; intmain(){ scanf("%d", &T); while (T--) { int n, k; scanf("%d%d", &n, &k); int c = 0, r = 0; for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)a[i][j] = 0; int u = (int)ceil(1.0*k / n), d = k / n, rs = k % n; for (int i = 0; i < n; i++) { int nd; if (i < rs)nd = u; else nd = d; for (int j = 0; j < nd; j++) { a[i][c] = 1; c = (c + 1) % n; } } int ans; if (k%n == 0)ans = 0; else ans = 2; printf("%d\n", ans); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++)printf("%d", a[i][j]); puts(""); } } return0; }
E1. Asterism (Easy Version)
题意:给定一个数组,对它重新排列,初始有一个数 x ,要满足每次都比数组中对应位置大,每次比较完手里的数+1。f(x) 为初始数为 x 时有多少个可行的排列。要求找出所有 f(x) mod p 不为 0 的 x 。(2≤p≤n≤2000),(1≤ai≤2000)
本题可以枚举x,只要O(n)计算 f(x)。
对于第一个位置,可以选择小于等于 x 的数;第二个位置可以选择剩下的小于等于 x+1 的数。以此类推。
所以维护一个前缀和记录小于等于 i 的数的个数。由于每次比较完会少一个,所以乘 cnt[x+j]−j。