M - Matrix Construction
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
int matrix[1001][1001];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int cnt=0;
for(int p=2;p<=n+m;p++){
for(int i=1;i<=n;i++){
if(p-i<=m&&p-i>=1) matrix[i][p-i]=++cnt;
}
}
cout<<"Yes\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<matrix[i][j]<<' ';
}
cout<<'\n';
}
}
return 0;
}
J - Just another Sorting Problem
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
string s;
cin>>n>>s;
int cnt=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x!=i) cnt++;
}
if(n==2) cout<<"Alice\n";
else if(n==3){
if(cnt==2) cout<<s<<'\n';
else{
if(s=="Alice") cout<<"Bob\n";
else cout<<"Alice\n";
}
}
else{
if(cnt==2&&s=="Alice") cout<<"Alice\n";
else cout<<"Bob\n";
}
}
return 0;
}
H - Horizon Scanning
statements
#include <bits/stdc++.h>
using std::numeric_limits;
using std::abs, std::max, std::min, std::swap;
using std::pair, std::make_pair;
using std::tuple, std::make_tuple;
using std::vector, std::deque;
using std::set, std::multiset;
using namespace std;
using T=long double; //全局数据类型
constexpr T eps=1e-8;
constexpr T INF=numeric_limits<T>::max();
constexpr T PI=3.1415926535897932384l;
const int N=2e5+10;
// 点与向量
struct Point
{
T x,y;
bool operator==(const Point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const Point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const Point &a) const {return !(*this<a || *this==a);}
Point operator+(const Point &a) const {return {x+a.x,y+a.y};}
Point operator-(const Point &a) const {return {x-a.x,y-a.y};}
Point operator-() const {return {-x,-y};}
Point operator*(const T k) const {return {k*x,k*y};}
Point operator/(const T k) const {return {x/k,y/k};}
T operator*(const Point &a) const {return x*a.x+y*a.y;} // 点积
T operator^(const Point &a) const {return x*a.y-y*a.x;} // 叉积，注意优先级
int toleft(const Point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // to-left 测试
T len2() const {return (*this)*(*this);} // 向量长度的平方
T dis2(const Point &a) const {return (a-(*this)).len2();} // 两点距离的平方
int quad() const // 象限判断 0:原点 1:x轴正 2:第一象限 3:y轴正 4:第二象限 5:x轴负 6:第三象限 7:y轴负 8:第四象限
{
if (abs(x)<=eps && abs(y)<=eps) return 0;
if (abs(y)<=eps) return x>eps ? 1 : 5;
if (abs(x)<=eps) return y>eps ? 3 : 7;
return y>eps ? (x>eps ? 2 : 4) : (x>eps ? 8 : 6);
}
// 必须用浮点数
T len() const {return sqrtl(len2());} // 向量长度
T dis(const Point &a) const {return sqrtl(dis2(a));} // 两点距离
T ang(const Point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));} // 向量夹角
Point rot(const T rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 逆时针旋转（给定角度）
Point rot(const T cosr,const T sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 逆时针旋转（给定角度的正弦与余弦）
};
// 极角排序
struct Argcmp
{
bool operator()(const Point &a,const Point &b) const
{
const int qa=a.quad(),qb=b.quad();
if (qa!=qb) return qa<qb;
const auto t=a^b;
// if (abs(t)<=eps) return a*a<b*b-eps; // 不同长度的向量需要分开
return t>eps;
}
};
Point p[N];
T change(Point x){
T angle=x.ang(Point{1,0});
if(x.quad()==0||x.quad()==1||x.quad()==2||x.quad()==3||x.quad()==4) return angle;
else return 2*PI-angle;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
long long x,y;
cin>>x>>y;
p[i].x=x,p[i].y=y;
}
if(n==k) cout<<fixed<<setprecision(10)<<2*PI<<'\n';
else{
sort(p,p+n,Argcmp());
if(change(p[0])==change(p[n-1])) cout<<fixed<<setprecision(10)<<2*PI<<'\n';
else{
T ans=0;
for(int i=0;i<n;i++){
T ang1=change(p[i]);
T ang2=change(p[(i+k)%n]);
if((i+k)%n>i) ans=max(ans,ang2-ang1);
else ans=max(ans,ang2-ang1+2*PI);
}
cout<<fixed<<setprecision(10)<<ans<<'\n';
}
}
}
return 0;
}
C - Coin
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
int get_round(int n,int k){
int res=0;
while(n>1){
int tmp=(n+k-1)/k;
int x=min((n-1)/tmp,(n-k*(tmp-1)+tmp-1)/tmp);
res+=x;
n-=x*tmp;
}
return res;
}
int get_pos(int n,int k,int r){
int pos=1;
while(r){
int tmp=(pos+k-2)/(k-1);
int x=min(r,(tmp*(k-1)-pos)/tmp+1);
pos+=x*tmp;
r-=x;
}
return pos;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int r=get_round(n,k);
cout<<get_pos(n,k,r)<<'\n';
}
return 0;
}
G - GCD
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
queue<array<int,3>> q;
q.push({a,b,0});
while(q.size()){
auto [x,y,s]=q.front();
q.pop();
if(x==0||y==0){
cout<<s+1<<'\n';
break;
}
int g=__gcd(x,y);
q.push({x-g,y,s+1});
q.push({x,y-g,s+1});
}
}
return 0;
}
E - Extracting Weights
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> f_u,f_v,id;
int gauss(vector<vector<int>> a)
{
int r, c;//分别表示行、列
int n=a.size(),m=a[0].size();
for (r = 0, c = 0; c < m; c++)
{
// 第一步：找出第c列中为1的任意一行
int t = r;
for (int i = r; i < n; i++)
if (a[i][c]) { t = i; break; }
if (!a[t][c]) continue;//如果所有方程的这一列都为0那么不进行操作
//第二步：将这一行换至第一行(未确定方程的第一行)，即第r行
swap(a[t],a[r]);swap(f_u[t],f_u[r]);swap(f_v[t],f_v[r]);
swap(id[t],id[r]);
//第三步：将这一行之后的每一行的第c列的数变成0
for (int i = r + 1; i < n; i++)
if (a[i][c])
for (int j = c; j < m; j++)
a[i][j] ^= a[r][j];
r++;//处理完当前行，进入下一行
}
return r;
}
int cal(vector<vector<int>>& a)//返回0表示有唯一解，1表示有无穷多组解，2表示无解
{
int n=a.size();
int r, c;//分别表示行、列
for (r = 0, c = 0; c < n; c++)
{
//第一步：找出第c列中为1的任意一行
int t = r;
for (int i = r; i < n; i++)
if (a[i][c]) { t = i; break; }
if (!a[t][c]) continue;//如果所有方程的这一列都为0那么不进行操作
//第二步：将这一行换至第一行(未确定方程的第一行)，即第r行
for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);
//第三步：将这一行之后的每一行的第c列的数变成0
for (int i = r + 1; i < n; i++)
if (a[i][c])
for (int j = c; j <= n; j++)
a[i][j] ^= a[r][j];
r++;//处理完当前行，进入下一行
}
if (r < n)
{
for (int i = r; i < n; i++)
if (a[i][n]) return 2;
return 1;
}
for (int i = n - 1; i >= 0; i--)
for (int j = i + 1; j < n; j++){
if(a[i][j]){
a[i][n] ^=a[j][n];//只有当a[i][j]为1时才需要异或！
a[i][j]=0;
}
}
return 0;
}
int h[300],ne[600],to[600],idx=0;
void add(int a,int b){
to[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
int dep[300],f[300];
void dfs(int u,int fa){
f[u]=fa,dep[u]=dep[fa]+1;
for(int i=h[u];~i;i=ne[i]){
int v=to[i];
if(v==fa) continue ;
dfs(v,u);
}
}
vector<int> path(int x,int y){
vector<int>res;
if(dep[x]<dep[y])swap(x,y);
while(dep[x]!=dep[y]){
res.push_back(x);
x=f[x];
}
while(x!=y){
res.push_back(x);
res.push_back(y);
x=f[x];
y=f[y];
}
res.push_back(x);
return res;
}
vector<vector<int>> a;
signed main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) h[i]=-1;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}
f_u.resize(n*n+1),f_v.resize(n*n+1),id.resize(n*n+1);
int cnt_length_k=0;
dfs(1,0);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
auto p=path(i,j);
if(p.size()==k+1){
vector<int> tmp(n-1,0);
for(int dot:p)
if(dot!=1) tmp[dot-2]=1;
a.push_back(tmp);
f_u[cnt_length_k]=i,f_v[cnt_length_k]=j;
id[cnt_length_k]=cnt_length_k;
cnt_length_k++;
}
}
}
if(cnt_length_k+1<n-1) cout<<"No\n";
else{
int cnt=gauss(a);
if(cnt==n-1){
cout<<"Yes\n";
cout<<"? "<<n-1<<' ';
for(int i=0;i<n-1;i++){
cout<<f_u[i]<<' '<<f_v[i]<<' ';
}
cout<<endl;
vector<vector<int>> mat;
for(int i=0;i<n-1;i++){
int rsp;
cin>>rsp;
a[id[i]].push_back(rsp);
mat.push_back(a[id[i]]);
}
cal(mat);
cout<<"! ";
for(int i=0;i<n-1;i++) cout<<mat[i][n-1]<<' ';
cout<<endl;
}
else cout<<"No\n";
}
return 0;
}
I - Items
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000007;
const int p = 998244353, gg = 3, ig = 332738118, img = 86583718;
const int mod = 998244353;
template <typename T>void read(T &x)
{
x = 0;
int f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
x *= f;
}
int qpow(int a, int b)
{
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
namespace Poly
{
#define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
#define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
#define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
#define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了
typedef vector<int> poly;
const int G = 3;//根据具体的模数而定，原根可不一定不一样！！！
//一般模数的原根为 2 3 5 7 10 6
const int inv_G = qpow(G, mod - 2);
int RR[N], deer[2][21][N], inv[N];
void init(const int t) {//预处理出来NTT里需要的w和wn，砍掉了一个log的时间
for(int p = 1; p <= t; ++ p) {
int buf1 = qpow(G, (mod - 1) / (1 << p));
int buf0 = qpow(inv_G, (mod - 1) / (1 << p));
deer[0][p][0] = deer[1][p][0] = 1;
for(int i = 1; i < (1 << p); ++ i) {
deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆
deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
}
}
inv[1] = 1;
for(int i = 2; i <= (1 << t); ++ i)
inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
}
int NTT_init(int n) {//快速数论变换预处理
int limit = 1, L = 0;
while(limit <= n) limit <<= 1, L ++ ;
for(int i = 0; i < limit; ++ i)
RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
return limit;
}
void NTT(poly &A, int type, int limit) {//快速数论变换
A.resize(limit);
for(int i = 0; i < limit; ++ i)
if(i < RR[i])
swap(A[i], A[RR[i]]);
for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
int len = mid >> 1;
for(int pos = 0; pos < limit; pos += mid) {
int *wn = deer[type][j];
for(int i = pos; i < pos + len; ++ i, ++ wn) {
int tmp = 1ll * (*wn) * A[i + len] % mod;
A[i + len] = ck(A[i] - tmp + mod);
A[i] = ck(A[i] + tmp);
}
}
}
if(type == 0) {
for(int i = 0; i < limit; ++ i)
A[i] = 1ll * A[i] * inv[limit] % mod;
}
}
poly poly_mul(poly A, poly B) {//多项式乘法
int deg = A.size() + B.size() - 1;
int limit = NTT_init(deg);
poly C(limit);
NTT(A, 1, limit);
NTT(B, 1, limit);
for(int i = 0; i < limit; ++ i)
C[i] = 1ll * A[i] * B[i] % mod;
NTT(C, 0, limit);
C.resize(deg);
return C;
}
poly poly_conv(const poly &A, const poly &B, int nn) {
poly C = poly_mul(A, B);
poly res(2 * nn + 1, 0);
for (int i = nn; i < 3 * nn + 1 && i < (int)C.size(); ++i) {
res[i - nn] = C[i];
}
return res;
}
poly poly_inv(poly &f, int deg) {//多项式求逆
if(deg == 1)
return poly(1, qpow(f[0], mod - 2));
poly A(f.begin(), f.begin() + deg);
poly B = poly_inv(f, (deg + 1) >> 1);
int limit = NTT_init(deg << 1);
NTT(A, 1, limit), NTT(B, 1, limit);
for(int i = 0; i < limit; ++ i)
A[i] = B[i] * (2 - 1ll * A[i] * B[i] % mod + mod) % mod;
NTT(A, 0, limit);
A.resize(deg);
return A;
}
poly poly_dev(poly f) {//多项式求导
int n = f.size();
for(int i = 1; i < n; ++ i) f[i - 1] = 1ll * f[i] * i % mod;
return f.resize(n - 1), f;//f[0] = 0，这里直接扔了,从1开始
}
poly poly_idev(poly f) {//多项式求积分
int n = f.size();
for(int i = n - 1; i ; -- i) f[i] = 1ll * f[i - 1] * inv[i] % mod;
return f[0] = 0, f;
}
poly poly_ln(poly f, int deg) {//多项式求对数
poly A = poly_idev(poly_mul(poly_dev(f), poly_inv(f, deg)));
return A.resize(deg), A;
}
poly poly_exp(poly &f, int deg) {//多项式求指数
if(deg == 1)
return poly(1, 1);
poly B = poly_exp(f, (deg + 1) >> 1);
B.resize(deg);
poly lnB = poly_ln(B, deg);
for(int i = 0; i < deg; ++ i)
lnB[i] = ck(f[i] - lnB[i] + mod);
int limit = NTT_init(deg << 1);//n -> n^2
NTT(B, 1, limit), NTT(lnB, 1, limit);
for(int i = 0; i < limit; ++ i)
B[i] = 1ll * B[i] * (1 + lnB[i]) % mod;
NTT(B, 0, limit);
B.resize(deg);
return B;
}
poly poly_sqrt(poly &f, int deg) {//多项式开方
if(deg == 1) return poly(1, 1);
poly A(f.begin(), f.begin() + deg);
poly B = poly_sqrt(f, (deg + 1) >> 1);
poly IB = poly_inv(B, deg);
int limit = NTT_init(deg << 1);
NTT(A, 1, limit), NTT(IB, 1, limit);
for(int i = 0; i < limit; ++ i)
A[i] = 1ll * A[i] * IB[i] % mod;
NTT(A, 0, limit);
for(int i =0; i < deg; ++ i)
A[i] = 1ll * (A[i] + B[i]) * inv[2] % mod;
A.resize(deg);
return A;
}
poly poly_pow_special(poly f, int k) {//多项式快速幂
f = poly_ln(f, f.size());
for(auto &x : f) x = 1ll * x * k % mod;
return poly_exp(f, f.size());
}
poly poly_pow(poly f, long long k) {
int n = f.size();
// 1. 找到第一个非零项 h
int h = -1;
for (int i = 0; i < n; ++i) {
if (f[i] != 0) {
h = i;
break;
}
}
// 若全为 0，则幂次也为 0
if (h == -1) return poly(n, 0);
// 2. 计算 a[h] 的逆元和 a[h]^k
int ih = qpow(f[h], mod - 2);
int hk = qpow(f[h], k);
// 3. 构造去掉前导 0 的 f' = f(x) / (x^h * a[h])
poly g(n - h, 0);
for (int i = 0; i + h < n; ++i)
g[i] = 1ll * f[i + h] * ih % mod;
// 4. 对 f' 求 ln，再乘 k，再 exp
poly ln_g = poly_ln(g, n - h);
for (auto &x : ln_g)
x = 1ll * x * (k % mod) % mod;
poly res = poly_exp(ln_g, n - h);
// 5. 恢复缩放项：乘上 a[h]^k，并左移 h*k 位
int shift = 1ll * h * k;
poly ans(n, 0);
for (int i = 0; i + shift < n && i < (int)res.size(); ++i)
ans[i + shift] = 1ll * res[i] * hk % mod;
return ans;
}
}
using Poly::poly;
using Poly::poly_conv;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
Poly::init(20);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int B = m / n;
int m_prime = m - B * n;
poly f(2 * n + 1, 0);
int offset = n;
for(int i = 1; i <= n; i++){
int w;
cin>>w;
w -= B;
int idx = w + offset;
if(idx >= 0 && idx < 2 * n + 1){
f[idx] = 1;
}
}
poly res(2 * n + 1, 0);
res[offset] = 1;
poly base = f;
int tt = n;
while(tt){
if(tt & 1){
res = poly_conv(res, base, n);
}
base = poly_conv(base, base, n);
tt >>= 1;
}
if(res[m_prime + offset]) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
