1、对于一棵树上的一个节点$u$，定义$f(u)$表示树上距离$u$最远的节点到$u$的距离。给出每个节点的$f$值，构造出这棵树。
思路：找到树的主干，然后不在主干上的节点一定可以连接到主干的某个节点上。
#include <iostream>
#include <map>
#include <string>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <string.h>
#include <fstream>
#include <sstream>
using namespace std;
const int N=1000005;
const int mod=1000000007;
class TreeDistanceConstruction
{
int a[111];
int get(int t,vector<pair<int,int>> &p)
{
for(int i=0;i<(int)p.size();++i)
{
if(p[i].first==t)
{
if(!a[p[i].second])
{
a[p[i].second]=1;
return p[i].second;
}
}
}
return -1;
}
public:
vector<int> construct(vector<int> d)
{
const int n=(int)d.size();
vector<pair<int,int>> p;
for(int i=0;i<n;++i)
{
p.push_back(make_pair(d[i],i));
}
sort(p.begin(),p.end());
vector<int> ans;
const int Max=p.back().first;
const int Min=p[0].first;
if(Min<(Max+1)/2) return ans;
if(Min>(Max+1)/2) return ans;
memset(a,0,sizeof(a));
if(Max&1)
{
const int K=(Max+1)>>1;
vector<int> ll,rr;
for(int i=K;i<=Max;++i)
{
int t=get(i,p);
if(t==-1) return ans;
ll.push_back(t);
t=get(i,p);
if(t==-1) return ans;
rr.push_back(t);
}
if(get(K,p)!=-1) return ans;
for(int i=0;i+1<(int)ll.size();++i)
{
ans.push_back(ll[i]);
ans.push_back(ll[i+1]);
}
for(int i=0;i+1<(int)rr.size();++i)
{
ans.push_back(rr[i]);
ans.push_back(rr[i+1]);
}
ans.push_back(ll[0]);
ans.push_back(rr[0]);
for(int i=0;i<(int)p.size();++i)
{
int id=p[i].second;
if(!a[id])
{
int len=p[i].first;
int nIndex=len-K-1;
ans.push_back(id);
ans.push_back(ll[nIndex]);
}
}
return ans;
}
else
{
const int K=Max>>1;
const int Kid=get(K,p);
if(Kid==-1) return ans;
if(get(K,p)!=-1) return ans;
vector<int> ll,rr;
for(int i=K+1;i<=Max;++i)
{
int t=get(i,p);
if(t==-1) return ans;
ll.push_back(t);
t=get(i,p);
if(t==-1) return ans;
rr.push_back(t);
}
for(int i=0;i+1<(int)ll.size();++i)
{
ans.push_back(ll[i]);
ans.push_back(ll[i+1]);
}
for(int i=0;i+1<(int)rr.size();++i)
{
ans.push_back(rr[i]);
ans.push_back(rr[i+1]);
}
ans.push_back(ll[0]);
ans.push_back(Kid);
ans.push_back(rr[0]);
ans.push_back(Kid);
ll.insert(ll.begin(),Kid);
for(int i=0;i<(int)p.size();++i)
{
int id=p[i].second;
if(!a[id])
{
int len=p[i].first;
int nIndex=len-K-1;
ans.push_back(id);
ans.push_back(ll[nIndex]);
}
}
return ans;
}
}
};
2、给定整数$n,K,v$，确定一个长度为$n$的序列$x$，满足$0leq x_{i}< K$且$x_{1}x_{2}...x_{n}mod K=v$。问这样的序列有多少个。现在给出很多$v$，对每一个$v$计算一个答案。
思路：（1）首先，假设$x$的前$n-1$个数已经确定，令$r=Gcd(prod_{i=1}^{n-1}x_{i},K)$。那么由$r,v$可以确定$x_{n}$的取值。由于$left (rcdot x_{n} ight )mod K=v$，那么$rcdot x_{n}=tK+v$，所以$Gcd(r,K)$可以整除$v$。由于$r$可以整除$K$，所以$r=Gcd(r,K)$一定可以整除$v$。那么对于某个$r$，$x_{n}$有$K/r$种选择，分别是$frac{tK+v}{r},0leq t<r$。
（2）由于$K$的约数不会太多，所以可以进行动态规划，设$f[i][j]$表示已经确定了$i$个$x$，它们的乘积与$K$的最大公约数为$j$。那么每次可以由$f[i][j]$转移到$f[i+1][k]$，其中$j$可以整除$k$。令$p=frac{k}{j}$，那么$q=Gcd(jcdot tp,K)$一定是$k$的倍数。那么进行容斥原理即可确定$x_{i+1}$ 种类使得$jcdot x_{i+1} mod K=k$。
#include <iostream>
#include <map>
#include <string>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <string.h>
using namespace std;
const int mod=1000000007;
int f[55][111111];
int d[111111];
vector<int> q[111111];
void add(int &x,int y)
{
x+=y;
if(x>=mod) x-=mod;
}
class ModEquation
{
public:
vector<int> count(int n,int K,vector<int> query)
{
vector<int> p;
for(int i=1;i*i<=K;++i) {
if(K%i==0) {
p.push_back(i);
if(i*i!=K) p.push_back(K/i);
}
}
sort(p.begin(),p.end());
for(int i=0;i<(int)p.size();++i) {
q[i].clear();
for(int j=i;j<(int)p.size();++j) {
if(p[j]%p[i]==0) {
q[i].push_back(j);
}
}
}
f[0][0]=1;
for(int i=1;i<=n-1;++i)
{
for(int j=0;j<(int)p.size();++j)
{
for(int k=0;k<(int)q[j].size();++k) {
d[q[j][k]]=(long long)f[i-1][j]*(K/(p[q[j][k]]/p[j]))%mod;
}
for(int k=(int)q[j].size()-1;k>=0;--k) {
const int u=q[j][k];
for(int t=1;t<(int)q[u].size();++t) {
const int v=q[u][t];
add(d[u],mod-d[v]);
}
}
for(int k=0;k<(int)q[j].size();++k) {
const int u=q[j][k];
add(f[i][u],d[u]);
d[u]=0;
}
}
}
vector<int> ans;
for(int i=0;i<(int)query.size();++i) {
const int v=query[i];
int tmp=0;
for(int j=0;j<(int)p.size();++j) {
if(v%p[j]==0) {
add(tmp,(long long)f[n-1][j]*p[j]%mod);
}
}
ans.push_back(tmp);
}
return ans;
}
};
3、构造一个有$n$个顶点的有向图，使得以0号节点开始，$n-1$号节点结束的哈密顿路径恰有$k$条。$2leq n leq 20$。
思路：如代码所示。路径上第二个节点是$n-2$时，有1条；否则若第二个节点是$n-3-i$，则有$2^{i}$条。
#include <iostream>
#include <map>
#include <string>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <string.h>
using namespace std;
class HamiltonianConstruction
{
public:
vector<string> construct(int k)
{
const int n=20;
vector<string> ans(n,string(n,'N'));
for(int i=2;i<=n-2;++i) ans[i][i-1]='Y';
for(int i=1;i<n;++i) {
for(int j=i+1;j<n;++j) ans[i][j]='Y';
}
for(int i=n-3;i>=1;--i,k>>=1) {
if(k&1) ans[0][i]='Y';
}
return ans;
}
};