ARC 172 E
先写一个暴力，看看有啥规律。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9;
ll pw(ll x,ll y){
ll res=1;
while (y){
if (y&1){
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll n;
cin>>n;
ll cur=1;
while (1){
if (pw(cur,cur)==n){
cout<<cur<<endl;
}
cur++;
}
return 0;
}
发现只能是 \(n,n+10^9,n+2\cdot 10^9\cdots\)，所以大胆猜想对于 \(\mod=10^{x\ge 2}\)，只有一个。事实上是对的。那么就可以从低到高确定。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll pw(ll x,ll y,const ll mod=1000000000){
ll res=1;
while (y){
if (y&1){
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while (t--){
ll x;
cin>>x;
ll fst=1;
while (pw(fst,fst)%100!=x%100){
fst++;
}
for (ll it=1000; it<=1000000000; it*=10ll){
for (int j=0; j<10; j++){
if (pw(j*it/10ll+fst,j*it/10ll+fst)%it==x%it){
fst=j*it/10ll+fst;
break;
}
}
}
assert(pw(fst,fst,1000000000)==x);
cout<<fst<<"\n";
}
return 0;
}
ARC 171 C
设 \(dp_{u,c,f}\) 为考虑 \(u\) 这个点，和他相连的（包括父亲）一共断了多少，现在有没有断父亲（\(0/1\)）。设 \(sum_{u,f}=\sum dp_{u,c,f}\)。则枚举到 \(u\) 的儿子 \(v\) 时，
-
\((u,v)\) 不断：\(dp'_{u,i,0}+=dp_{u,i,0}\cdot sum_{v,0}\)。
-
\((u,v)\) 断：\(dp'_{u,i,0}+=dp_{u,i-1,0}\cdot sum_{v,1}\cdot i,i\ge 1\)。
\(dp'_{u,i,1}\) 同理。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e3+3;
const ll mod = 998244353;
ll n,dp[N][N][2],sum[N][2];
ll _dp[N][2];
vector<int> g[N];
void dfs(int u,int fa){
dp[u][0][0]=1;
dp[u][1][1]=(fa!=0);
int ot=(fa!=0);
for (auto v : g[u]){
if (v!=fa){
dfs(v,u);
ot++;
for (int i=0; i<=ot; i++){
_dp[i][0]=dp[u][i][0],_dp[i][1]=dp[u][i][1];
dp[u][i][0]=dp[u][i][1]=0;
}
for (ll i=0; i<=ot; i++){
(dp[u][i][0]+=_dp[i][0]*sum[v][0]%mod)%=mod;
(dp[u][i][1]+=_dp[i][1]*sum[v][0]%mod)%=mod;
if (i>=1){
(dp[u][i][0]+=_dp[i-1][0]*sum[v][1]%mod*i%mod)%=mod;
(dp[u][i][1]+=_dp[i-1][1]*sum[v][1]%mod*i%mod)%=mod;
}
}
}
}
for (int i=0; i<=ot; i++){
(sum[u][0]+=dp[u][i][0])%=mod;
(sum[u][1]+=dp[u][i][1])%=mod;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<n; i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<sum[1][0]<<"\n";
return 0;
}
ARC 171 D
设 \(h_i\) 为原序列 \(1\sim i\) 的哈希值。容易发现对于任意的 \(h\)，总可以取到。\(\texttt{hash}(A_{l\sim r})=0\) 的条件是 \(h_l=h_{r+1}\)。
所以可以抽象成另一个问题：
-
有 \(n+1\) 个点，对于每一个限制，给 \(l_i,r_i+1\) 连边。
-
问有没有一种染色方法，用的颜色个数 \(\le P\)，并且使得有连边的点颜色不同。
这是一个经典问题。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m,B,P;
int e[18][18],nc[1<<17];
int dp[1<<17];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>P>>B>>n>>m;
for (int i=1; i<=m; i++){
int l,r;
cin>>l>>r;
e[l][r+1]=1;
e[r+1][l]=1;
}
for (int s=0; s<(1<<n+1); s++){
nc[s]=1;
for (int i=0; i<=n; i++){
if (s>>i&1){
for (int j=0; j<=n; j++){
if (s>>j&1){
if (e[i+1][j+1]){
nc[s]=0;
}
}
}
}
}
}
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for (int s=0; s<(1<<n+1); s++){
for (int t=s; t; t=(t-1)&s){
if (nc[t]){
dp[s]=min(dp[s],dp[t^s]+1);
}
}
}
if (dp[(1<<n+1)-1]<=P){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
return 0;
}
ARC 172 D
- tags：构造题中的调整法。
这么牛的题目！看了一个 hint。
官 hint 是：如果都是 \(=\)，怎么做？
显然有一个构造满足两个点 \(\texttt{dis}=\sqrt{2}\)。这是令 \(p_1=\{1,0,0,0,0,\cdots\},p_2=\{0,1,0,0,0,\cdots\},\cdots\)。
怎么全变为 \(<\)？考虑调整法。
即考虑 \(p_1=\{1+eps_{1,1},eps_{1,2},\cdots \},p_{2}=\{eps_{2,1},1+eps_{2,2},\cdots\}\cdots\)，其中 \(eps_{i,j}\) 是一个很小的数例如 \(10^{-7}\)。因为太小了，\(eps^2\) 可以视为 \(0\)。
那么，两个点 \(i,j\) 的距离为 \(\sqrt{2-(eps_{i,j}+eps_{j,i})+\sum_k (eps_{i,k}\cdot eps_{j,k})}\)，约等于 \(\sqrt{2-(eps_{i,j}+eps_{j,i})}\)。我们只需要这个值可以满足 \(<\) 的关系。也就是 \(eps_{i,j}+eps_{j,i}\) 怎么构造。
可以先令 \(eps_{j,i}(j>i)=0\)，只考虑 \(eps_{i,j}\)。可以令它为 \(10^{-7}\times rnk_{i,j}\)，其中 \(rnk_{i,j}\) 是第几大。这样就可以了。
因为题目要求是整数，那么都乘上一个大数就可以了。（如 \(10^7\)）
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 22;
const int inf = 9e7;
int n,rnk[N][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<=n*(n-1)/2; i++){
int a,b;
cin>>a>>b;
rnk[a][b]=n*(n-1)/2-i+1;
}
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
if (i==j){
cout<<inf+rnk[i][j]<<" ";
}
else{
cout<<rnk[i][j]<<" ";
}
}
cout<<"\n";
}
return 0;
}