【考试总结】2022-03-21
Board Game
将 \(k\) 个非法状态在棋盘上所有可能的出现位置表示成 \(nm\) 位的二进制数，做高维前缀和来标记非法
之后是一个平凡的 \(\rm SG\) 函数问题，不另赘述，但是复杂度过高
注意到 \(vis,\rm dp\) 数组中的元素的值域是 \(\{0,1\}\) 所以考虑将相邻的 \(64\) 个数压成一个 \(64\) 位 unsigned long long，这样子在高维前缀和的时候做一次 \(\rm OR\) 操作就可以实现 \(64\) 个位的转移
此时仍然需要处理一个数字内部的转移，这里子母集关系只会出现在 \(0\sim 63\) 之间，预处理 \(64\) 个 unsigned long long \(\rm sub_i\) 表示 \(0\sim 63\) 中哪些是 \(i\) 的子集
这样子每次找到 \(\rm sub_j\& vis_i\) 就可以得到数字内部的转移了
而后面 \(\rm DP\) 的部分也是类似的，预处理每个 \(0\sim 63\) 添加一个 \(1\) 能走到内部的哪个元素，转移判定为 \(1\) 的元素个数是不是等于集合大小即可
Code Display
int n,m,lim,k;
ull vis[1<<21],dp[1<<21];
char s[30][30];
inline void Vis_set(int pos) { vis[pos >> 6] |= 1ull << (pos & 63); }
inline ull Vis(int pos) { return vis[pos >> 6] >> (pos & 63) & 1; }
namespace Sub1{
bool vis[1<<22],dp[1<<22];
inline int dfs(int x){
if(vis[x]) return dp[x];
vis[x]=1;
int U=(lim-1)^x;
while(U){
int lb=U&(-U);
if(!dfs(x^lb)) return dp[x]=1;
U-=lb;
} return dp[x];
}
inline void main(){
while(k--){
int h=read(),w=read();
rep(i,1,h) scanf("%s",s[i]+1);
for(int dx=0;dx<=n-h;++dx){
for(int dy=0;dy<=m-w;++dy){
int st=0;
for(int i=1;i<=h;++i){
for(int j=1;j<=w;++j){
if(s[i][j]=='1') st|=1<<((i+dx-1)*m+j+dy-1);
}
}
vis[st]=1;
}
}
}
lim=1<<(n*m);
for(int p=2;p<=lim;p<<=1){
int len=p>>1;
for(int k=0;k Sub(64);
for(int i=0;i<64;++i){
Sub[i]|=1;
for(int j=i;j;j=(j-1)&i) Sub[i]|=1ull<>1;
for(int k=0;k>j&1) Sub[i^(1< bit(64);
rep(i,0,63) bit[i]=__builtin_popcountll(Sub[i]);
for(int i=lim-1;i>=0;--i){
for(int j=0;j>j&1)) dp[i]|=~dp[i^(1<=0;--j) if(!(vis[i]>>j&1)){
if(dp[i]>>j&1) continue;
if(__builtin_popcountll(dp[i]&Sub[j])!=bit[j]) dp[i]|=1ull<>j&1) dp[i]^=(1ull< Difference Query
首先注意给定的序列是排列
考察 \(f(x,x)\) 做若干步逆操作得到的形式可以发现 \(\exists p,\frac{x}{\rm gcd(x,y)}+\frac{y}{\rm gcd(x,y)}=2^p\Rightarrow f(x,y)=p\)，否则 \(f(x,y)=0\)
扫描线，对于每个 \(i\) 枚举 \(a_i\) 的因子作为 \(\rm gcd\)，再枚举 \(2^p\) 作为答案，找到所有带来贡献的数字在线段树上执行区间加法即可
回答完询问之后再把每个 \(a_i\) 放到其因子的标号为 \(\frac {a_i}d\) 的桶里面即可，空间复杂度是 \(\Theta(n\ln n)\) 的，加一些剪枝可以获得小常数
Code Display
const int N=1e5+10;
int ans[N],n,a[N],Q,Mx[N];
vector Div[N];
vector > > app[N];
struct Seg{
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
int fir[N<<2],len[N<<2],delt[N<<2];
inline void build(int p,int l,int r){
len[p]=r-l+1; if(l==r) return ;
int mid=(l+r)>>1; build(lson); build(rson);
return ;
}
inline void upd(int st,int ed,int fr,int d,int p=1,int l=1,int r=n){
if(st<=l&&r<=ed) return fir[p]+=(l-st)*d+fr,delt[p]+=d,void();
int mid=(l+r)>>1;
if(st<=mid) upd(st,ed,fr,d,lson); if(ed>mid) upd(st,ed,fr,d,rson);
return ;
}
inline int Query(int pos,int p=1,int l=1,int r=n){
int res=fir[p]+delt[p]*(pos-l); if(l==r) return res;
int mid=(l+r)>>1;
if(pos<=mid) return res+Query(pos,lson);
else return res+Query(pos,rson);
}
#undef ls
#undef rs
#undef lson
#undef rson
}T;
vector >qu[N];
signed main(){
freopen("func.in","r",stdin); freopen("func.out","w",stdout);
n=1e5;
rep(i,1,n){
for(int j=i;j<=n;j+=i) Div[j].emplace_back(i);
app[i].resize(n/i+2);
}
n=read();
rep(i,1,n) a[i]=read();
Q=read();
for(int i=1;i<=Q;++i){
int l=read(),r=read();
qu[r].emplace_back(l,i);
}
for(int i=1;i<=n;++i){
for(auto d:Div[a[i]]) if((a[i]/d)&1){
int quo=a[i]/d,p=1;
while((1<=(1< Minimal DFA
一个识别 \(\Sigma \in\{0,1\},L\subset \Sigma^n,L\neq \empty\) 的 \(\rm DFA\) 应当有如下几个性质：
- 可以将点分成 \(n+1\) 层，否则能识别的长度不唯一
下设 \(k_i\) 表示 \(\rm DFA\) 的第 \(i\) 层点的数量
-
\(k_i\le k_{i-1}\times |\Sigma|\)
-
\(k_i+1\le (k_i+1)^2\)
这个是因为第 \(i\) 层的每个点有 \((k_{i+1}+1)^2\) 种后继连接方式，\(+1\) 是不选择任何连边，但是不能两个都不连，也不能出现两个相同，所以得到解释
第二条从层数小向层数大限制，第三条从层数大到小限制，那么一个高精度类即可解决
找到第一个 \(k_{i+1}\neq 2k_{i}\) 的 \(i\) 来进行后面两问的计算：
（下简记从某个第 \(i+1\) 层的点走到终点的路径上 \(|\Sigma_E|\) 的乘积为其走法）
如果 \(k_{i+1}\ge k_i\) 那么可以证明 \(k_{i+1}=2k_i-1\)，将 \(i+1\) 层每个点连接出边之后 \(i\) 层的点只剩下 \(1\) 的度，最大就是再连 \(2^{n-i}\) 的走法的点，最小就是不连
否则考虑先给所有第 \(i+1\) 层的点连接出边，根据最大化/最小化需求将余下的出边分配终点，以最大化为例
开始考虑每个 \(i+1\) 层的点分配出边是涉及的 \(i\) 层点的另一个出边都连向 \(2^{n-i}\) 走法的点
从大到小枚举剩下点连出去的两条边的走法之和 \(v\)，这时候使用组合数即可得到方案 \(\binom{2^{n-i+1}}v\)，注意要减去已经走过的方案数 \([v\ge 2^{n-i}]\binom{2^{n-i}}{v-2^{n-i}}\)
最小化同理，一开始强制连出的点不选第二个终点，后面枚举边权从小往大即可
Code Display
const int Bas=1e8;
struct node{
vector a;
inline int size(){return a.size();}
inline void adjust(){
int siz=a.size();
for(int i=0;i=Bas){
a.emplace_back(a[siz-1]/Bas);
a[siz-1]%=Bas;
++siz;
}
while(siz>1&&!a[siz-1]) a.pop_back(),--siz;
return ;
}
inline void init(int x){
a.clear();
while(x) a.push_back(x%Bas),x/=Bas;
return ;
}
//Attention: const node b is not available here!
//we Use function size which may change itself though it actually don't
bool operator <(node b)const{
if(a.size()!=b.size()) return a.size()=1;--v){
node cur=C[1<<(Div+1)][v];
if(v>=(1<=1;--i){
node tmp=A[i+1]+1; tmp=tmp*tmp-1;
if(A[i]<=tmp) break;
A[i]=tmp;
}
for(int i=1;i<=n+1;++i) ans=ans+A[i];
ans.output();
for(int i=1;i<=n;++i) if(A[i]*2!=A[i+1]){Div=i; break;}
if(A[Div]