#include<bits/stdc++.h>
using namespace std;
const int N=3; //矩阵维数
typedef vector<pair<string,int> > VSI;
typedef pair<string,int> SI;
//带参数的矩阵乘法
void mul(VSI ans[N][N],SI a[N][N])
{
VSI res[N][N]; //临时矩阵
//模拟
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
{
string s2=a[k][j].first; //参数
int i2=a[k][j].second; //系数
if(i2==0) continue; //优化，f(x)*0=0，不必继续往下计算
for(int l=0;l<ans[i][k].size();l++)
{
string s1=ans[i][k][l].first;
int i1=ans[i][k][l].second;
if(s2!="1"/*省略1*/) s1+=s2;
res[i][j].push_back({s1,i1*i2}); //参数：字符串直接加在后面；系数：直接相乘
}
}
//将临时矩阵复制到答案矩阵
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
ans[i][j].clear();
for(int k=0;k<res[i][j].size();k++) ans[i][j].push_back(res[i][j][k]);
}
return ;
}
//计数排序
unordered_map<char,int> h;
void Hash(char a)
{
if(!h.count(a)) h[a]=1;
else h[a]++;
return ;
}
//计数排序求最简单项式
string get_min(string a)
{
string res;
h.clear();
for(int i=0;i<a.length();i++) Hash(a[i]);
for(char x='a';x<='z';x++)
for(int i=1;i<=h[x];i++)
if(x!='h') res.push_back(x);
return res;
}
//化简
void simplify(VSI ans[N][N])
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
//对组成多项式的单项式求最简式
for(int k=0;k<ans[i][j].size();k++) ans[i][j][k].first=get_min(ans[i][j][k].first);
//排列项
sort(ans[i][j].begin(),ans[i][j].end());
//合并同类项
VSI res; //临时矩阵
int ne=0,num=0;
for(int k=0;k<ans[i][j].size();k=ne)
{
num=ans[i][j][k].second;
ne=k+1;
while(ne<ans[i][j].size() && ans[i][j][k].first==ans[i][j][ne].first)
{
num+=ans[i][j][ne].second;
ne++;
}
res.push_back({ans[i][j][k].first,num});
}
//将临时矩阵复制到答案矩阵
ans[i][j].clear();
for(int k=0;k<res.size();k++) if(res[k].second!=0) ans[i][j].push_back(res[k]);
}
return ;
}
//输出
void print(VSI ans[N][N])
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
for(int k=0;k<ans[i][j].size();k++) cout<<ans[i][j][k].second<<ans[i][j][k].first<<' ';
puts("");
}
puts("");
return ;
}
int main()
{
//填入第一个矩阵
VSI ans[N][N];
ans[0][0].push_back({"b",1});
ans[0][1].push_back({"a",1});
ans[0][2].push_back({"0",0});
ans[1][0].push_back({"a",-1});
ans[1][1].push_back({"b",1});
ans[1][2].push_back({"0",0});
ans[2][0].push_back({"0",0});
ans[2][1].push_back({"0",0});
ans[2][2].push_back({"1",1});
//填入后面相乘的矩阵
SI op1[N][N]=
{
{{"d",1},{"0",0},{"c",1}},
{{"0",0},{"1",1},{"0",0}},
{{"c",-1},{"0",0},{"d",1}}
};
SI op2[N][N]=
{
{{"1",1},{"0",0},{"0",0}},
{{"0",0},{"f",1},{"e",-1}},
{{"0",0},{"e",1},{"f",1}}
};
SI op3[N][N]=
{
{{"d",1},{"0",0},{"c",-1}},
{{"0",0},{"1",1},{"0",0}},
{{"c",1},{"0",0},{"d",1}}
};
SI op4[N][N]=
{
{{"b",1},{"a",-1},{"0",0}},
{{"a",1},{"b",1},{"0",0}},
{{"0",0},{"0",0},{"1",1}}
};
//带参数的矩阵乘法
mul(ans,op1);
mul(ans,op2);
mul(ans,op3);
mul(ans,op4);
//化简
simplify(ans);
//输出
print(ans);
return 0;
}分类： 未分类
「QOJ2342」鸭性统计 duck
首先，聪明的你应该把$duck$反过来读：就是“可达”。
所以这道题就是“可达性统计”的模板题。
只不过，这道题把数据加强到了 $10^5$，并且本题中的图可能存在环。
就是这两个问题，我们一个一个来处理。
对于图中存在环的问题，我们只需要 $\texttt{tarjan}$一下，缩点染色一下就行了，因为在一个环内的两个点肯定两两互相可达，我们把他染成一个颜色并没有问题，其他的操作正常进行，$\texttt{tarjan}$ 缩点肯定大家都会。
接着，我们要对付 $10^5$ 的数据。
对于简单版的可达性统计，我们是建了 bitset<1005> b[1005]，b[x][y] 代表的是否能从 $x$ 点到达 $y$ 点，我们用 $\texttt{bitset}$，是为了把第二维压成一个 01 串，从而降低空间。但是对于 $10^5$ 的数据我们把 $\texttt{bitset}$ 建出来：bitset<100005> b[100005]。算一下，上了 $1000\texttt{MiB}$，肯定不可取。
那怎么办呢？
这里就要用到一个很常用的，很重要的技巧：牺牲时间复杂度来补救空间复杂度！
因为我们发现，时间复杂度太优秀了，空间复杂度太菜了。于是我们想到一个类似分块的思想来解决这个问题。
我们可以把 $Ｑ$ 次询问分成 $k$ 段，每一段长为 $len$，然后一段一段地解决，一段一段地处理，我们将每一段询问中 $(u,v)$ 的 $v$ 做一个离散化操作，使得 $\texttt{bitset}$ 的第二维空间降下来，因为这一段最后真正有用的就这 $len$ 个点能否到达，至于其他点能否到达我们不在乎，将它们都看作编号为 0 即可。每一段询问都进行同样的操作，就可以通过本题。其实这样的方法也不叫分块，它就是把一个问题分成了几段，依次处理。
当然，在保证空间复杂度的前提下，$k$ 越小越好。
$code:$
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#define reg register
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
inline int read()
{
int x=0,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();
}
return x*f;
}
int n,m,Q;
int wugui=0;
int head1[maxn];
struct node
{
int to;
int nxt;
}edge[maxn];
void add(int x,int y)
{
wugui++;
edge[wugui].to=y;
edge[wugui].nxt=head1[x];
head1[x]=wugui;
}
int in[maxn];
queue<int> q;
vector<int> v[maxn];
int low[maxn];
int dfn[maxn];
int cnt=0;
int s[maxn];
int col[maxn];
int color=0;
int vis[maxn];
int index1=0;
struct Query
{
int x,y;
}ask[maxn];
//tarjan
void tarjan(int x)
{
low[x]=dfn[x]=++index1;
vis[x]=1;
s[++cnt]=x;
for(reg int i=0;i<(int)v[x].size();i++)
{
int t=v[x][i];
if(dfn[t]==0)
{
tarjan(t);
low[x]=min(low[x],low[t]);
}
else
{
if(vis[t]==1)
low[x]=min(low[x],dfn[t]);
}
}
if(dfn[x]==low[x])
{
int v;
color++;
do
{
v=s[cnt];
cnt--;
col[v]=color;
vis[v]=0;
}
while(v!=x);
}
}
bitset<20005> a[maxn];
int re_in[maxn];
int tot=0;
int b[maxn];
int id[maxn];
int Get(int x)
{
return lower_bound(s+1,s+1+tot,x)-s;
}
int order[maxn];
int ORDER=0;
void Work(int l,int r)
{
// re_sort & Get_id
tot=0;
int fuck=0;
for(reg int i=l;i<=r;i++)
b[++fuck]=col[ask[i].y];
sort(b+1,b+1+fuck);
b[0]=-1e9;
for(reg int i=1;i<=fuck;i++)
{
if(b[i]!=b[i-1])
s[++tot]=b[i];
}
// bitset_dp & topo
for(reg int i=1;i<=color;i++)
{
id[i]=Get(i);
if(s[id[i]]!=i)
id[i]=0;
a[i].reset();
if(re_in[i]==0)
{
q.push(i);
int x=id[i];
a[i][x]=1;
}
}
for(reg int j=1;j<=ORDER;j++)
{
int point=order[j];
int x=id[point];
a[point][x]=1;
for(reg int i=head1[point];i;i=edge[i].nxt)
{
int t=edge[i].to;
a[t] |= a[point];
}
}
// Get_ans
for(reg int i=l;i<=r;i++)
{
int x=col[ask[i].x];
int y=col[ask[i].y];
if(a[x][id[y]])
cout<<"Y";
else
cout<<"N";
}
}
int main()
{
//tarjan
n=read(),m=read(),Q=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
v[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
tarjan(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<(int)v[i].size();j++)
{
int x=col[i];
int y=col[v[i][j]];
if(x==y)
continue;
in[x]++;
add(y,x);
}
}
//topo_sort
for(int i=1;i<=color;i++)
re_in[i]=in[i];
for(reg int i=1;i<=color;i++)
{
if(in[i]==0)
q.push(i);
}
while(!q.empty())
{
int point=q.front();
q.pop();
order[++ORDER]=point;
for(reg int i=head1[point];i;i=edge[i].nxt)
{
int t=edge[i].to;
in[t]--;
if(in[t]==0)
q.push(t);
}
}
// divide segments
for(int i=1;i<=Q;i++)
ask[i].x=read(),ask[i].y=read();
int len=20000;
int now=1;
while(true)
{
if(now+len-1<Q)
{
Work(now,now+len-1); // Get_ans
now=now+len;
}
else
{
Work(now,Q); // Get_ans
break;
}
}
return 0;
}
FZOI WC 2020 抢救计划
为了抢救各位被文化课耽误的信息学，kal0rona 出了一套抢救计划。