过去一年我都做了些什么呢...如果现在不记下来的话之后会不会完全忘记了呢？        如果写能够看懂的内容，反而有可能会造成成误解；这样来看不如写一些意义完全含混不清的内容吧！ ...继续阅读 (14)

题目大意：给定一颗无穷大的完全二叉树，根节点的标号为$1$，对于每个节点若其标号为$x$，则其左儿子标号为$2x$，右儿子标号为$2x+1$。同时再给定$S$，求树上有多少条路径使得路径上节点的标号和恰为$S$。数据范围$S\leq{10^{15}}$。  ...继续阅读 (6)

（反正也没有人看我博客，在这里发泄点负能量总没什么问题吧垃圾没有别的地方可以去了，看起来只有去图书馆了。但是图书馆呢，明显不是垃圾桶啊。这样感觉很愧疚啊。至少也要有地方去啊，那么就呆在这里吧。 无论到了哪里，对谁来说，都是无关紧要的人呢。根本没有什么寻找存在感的意义呢，就算再努力去找也找不到的吧。如同暗淡的星辰一样，遥望着亿万里外的璀璨银河。如果完全没有价值的话，意味着也不能从别人那里收获认同与爱呢。真遗憾，显然我就是那种完全没有价值的人哦。 ...继续阅读 (12)

9.30退课截止思修知乎上水4发10.7 大数据与机器智能，使用C++实现位图索引，通过测试并提交到gitlab上。10.8西哲导修课Subtask1:合作制作柏拉图、苏格拉底的生平经历、哲学思想以及对后人的影响Subtask2:思考哲学问题10.11线性代数作业4、5信概作业3离散数学作业310.12微积分作业4、510.31英语作文 *好好学英语！*至少也听一点讲座！ ...继续阅读 (11)

题目大意：反正已经有翻译了，就自己去看咯。算法讨论：首先是每行每列都有一个跟答案相关的限制，但是我们并不知道答案，所以我们可以枚举这个限制，算出在这个限制下的答案，然后比较在这个答案下的限制和枚举的限制，若前者不小于后者则可以认为这个答案是合法的。最终的答案一定会出现在这些合法的答案中。不难想到把$n$行$n$列拆成$2n$个点，然后从$S$到左侧的行点，从右侧的列点到$T$各连接一条流量为枚举的限制费用为$0$的边。然后对于第$i$行第$j$列，从左侧的第$i$个行点到右侧的第$j$个列点连边，若为'.'则连接一条流量为$1$费用为$1$的边，若为'C'则连接一条流量下界为1上界为1费用为1的边，若为'/'则什么也不连。但是还需要满足的是第$i$行和第$i$列的零件数目相等。我们考虑一种连边：从第$i$个行点到第$i$个列点连一条流量为$\infty$费用为$0$的边，然后求这个网络的最大费用最大流就是答案。这样是怎样保证数目相等这个限制的呢？可以发现现在流网络的最大流必为$n\times{枚举的限制}$。这是在不考虑任何零件的边之后得到的。那么对于第$i$个行点，设当前枚举限制为$c$，他本应该把从$S$流来的$c$流量，通过那条$\infty$边全部流到第$i$个列点，随后全部流到$T$。但是第$i$个行点可能向一些列节点流了一些流量（放置零件），假设为$x$（那么此时第$i ...继续阅读 (52)

2015/10/8最近沉迷于看LOL的同人小说，尤其喜欢看男刀的CP。看了男刀和卡特、光女、蛇女、刀妹的CP感觉心里暖暖的，不知道为什么。就像我自己，以前也总是喜欢带着兜帽藏在阴影里面，也许男刀的经历让我的内心产生了共鸣了吧。不要拽了吧，我的心中哪有什么可以称之为阴暗的角落的地方呢？但其实，这样的阴影每个人都总是会有的。身为一个人就不可能没有恐惧，没有悲伤。所以不能贪心，就算什么都没有拥有，也依然要珍惜别人带来的温暖。尽管有时，那温暖并不浪漫，也没有梦幻的色彩。那就先从我自己开始吧，尽管现在的我被自己认为是“会让过去的自己瞧不起的家伙”。但是呢。你绝不是一无是处。你是我最重要的人。我相信你。 ...继续阅读 (56)

我也不知道什么时候开始用上Latex的。。。应该是当时觉得公式非常厉害，又加之集训队论文也是要求用这东西的，就入坑了。但由于鄙人涉之甚浅，因而并不能做出什么厉害的效果，这里也大概只是入门罢了。  ...继续阅读 (51)

题解：现在终于还算是明白了。首先将边的存在性定义为两种颜色，这样就变成了一个Polya的经典问题。但是如何考虑边的置换群呢？我们首先考虑点的置换群。点的置换显然有$O(n!)$种，但我们可以按照每个循环的大小进行分组，最终发现组数还是能够接受的。考虑一个组的点置换，我们最终将方案数乘以这个组内有多少置换就行了。这一步可以用简单的组合数学知识来解决。现在考虑如何将点置换转化为边置换，即将所有边划分为若干组可以轮换的边。考虑那种两个端点在同一个点循环的边，则如果点循环的大小为$n$，我们可以分为差值分别为$1,2,...,\lfloor\frac{n}{2}\rfloor$的若干组。考虑那种两个端点在不同的点循环的边，如果两个点循环的大小分别为$n,m$,脑补一下可以发现会出现$gcd(n,m)$组边。这样的话，问题大概就得到了解决了。代码： ...继续阅读 (110)

题解：从高到低按位贪心，预处理前缀异或和，若想这一位为0的话则必须选择的终点位置前缀和这一位均为0。如果可以令这一位为0，则处理一下可选集合就行了。时间复杂度$O(nlogn)$。代码：#include<cstdio> #include<cctype> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; #define N 500010 ll a[N]; bool del[N]; int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #endif int n,m,i,j; cin>>n>>m; for(i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]^=a[i-1]; ll ans=0; bool ok; int cnt; for(i=59;i>=0;--i){ ok=1; if((a[n]>>i)&1) ok=0; e ...继续阅读 (102)

题解：就是一个最大团吧。随机一些贪心插入取最大值。这个算法效果还是很好的。正解貌似是一个二分图匹配？不过数学只是有点欠缺还是略过了。代码：#include<cstdio> #include<cctype> #include<cstring> #include<climits> #include<iostream> #include<algorithm> using namespace std; #define N 110 int x[N],y[N],p[N]; bool g[N][N]; int ans[N],num,q[N],cnt; int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #endif int n,d,i,j; cin>>n>>d; for(i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]); for(i=1;i<=n;++i) for(j=i+1;j<=n;++j) g[i][j]=g[j][i]=((x[i]-x[j])*(x[i]-x[j])+(y[ ...继续阅读 (134)

题解：考虑以某个元素开头的前缀gcd，至多只有log段。这是因为每一次gcd发生变化必然是原来答案的一个真约数，那么最多只有原来的一半。所以枚举起点不断二分找出所有段即可。利用RMQ预处理求区间的gcd，每次可以$O(1)$。于是时间复杂度$O(nlog^2n)$。然而事实上，我们直接暴力维护所有段即可，因为每次只需要将末尾添加一个数，且只有log段，暴力判断即可。这样就能做到$O(nlogn)$。我脑洞也是大了点。。。代码：#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; inline ll gcd(ll a,ll b){ return(!b)?a:gcd(b,a%b); } #define N 100010 ll f[N][17]; int len[N]; inline ll query(int l,int r){ return gcd(f[l][len[r-l+1]],f[r-(1<<len[r-l+1])+1][len[r-l+1]]); } int main(){ #ifnde ...继续阅读 (121)

题解：首先考虑如何对一个可逆矩阵求逆。据称有一个理论就是任意一个可逆矩阵都是单位矩阵通过基本行变换以及基本列变换形成的。毕竟我们这样搞肯定搞不出不可逆矩阵的吧。所以我们对矩阵进行消元变成单位矩阵，假设这个过程相当于乘上了一个矩阵$B$。也就是说：$A\times{B}=I$。事实上说明了$B=A^{-1}$。所以我们让一个单位矩阵也和矩阵$A$进行相同的基本变换，最终就能得到$A$的逆矩阵了。再加之BSGS那套理论就行了。这样求逆元和乘法的复杂度都是$O(n^3)$。这样复杂度就是$O(n^3\sqrt{p})$吧。有一些细节，比如利用hash表，以及预处理逆元。这里利用到了线性筛逆元大法好！比如我们想求$a$的逆元$a^{-1}$，并保证在此之前的逆元都已经被求出。不妨令$p=r\times{a}+q$,其中$0<q<a$（因为必然不整除），那么也就是说：$r\times{a}+q\equiv{0}\pmod{p}$两边同时乘以$q^{-1}$得到：$r\times{a}\times{q^{-1}}+1\equiv{0}\pmod{p}$移项得到：$-r\times{q^{-1}}\times{a}\equiv{1}\pmod{p}$于是得到：$a^{-1}\equiv{-r\times{q^{-1}}}\pmod{p}$而显然$q^{-1}$我们之前已经求出，于是这 ...继续阅读 (90)

题解：傻逼最小割。心血来潮写了个ISAP结果倒数第二的怨念。。。不错了呢，毕竟早上5点睡的觉，结果7点钟又去打篮球啊。不得不说人类真是充满活力呢。现在是8:50，我还能坚持几个小时呢？代码：#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; #define inf 0x3f3f3f3f struct Solver{ static const int V=100010; static const int E=1000010; int head[V],next[E],end[E],flow[E],ind; int gap[V],d[V],cur[V],stack[V],top; inline void reset(){ ind=top=0; memset(head,-1,sizeof head); } inline void addedge(int a,int b,int f){ int q=ind++; end[q]=b; next[q]=head[a]; head[a]=q; flow[q]=f; } in ...继续阅读 (50)

题解：首先注意到假如目前的树上能够插入$n$个节点，那么插入一个能够插入$m$个节点的节点，无论这个节点接在原来的一个位置上，还是这个节点成为新的树的根节点，这棵树都能够插入$n+m-1$个节点。也就是说，树的形态我们并不需要考虑，只需要考虑这棵树能够插入多少节点。我们考虑令$f[i][j]$表示前$i$种物品形成的树，树中能够插入$j$个节点的最大价值。显然利用背包就可以做了。我加了一点优化：对于$m=0$的节点最后一起贪心的考虑。虽然复杂度依然是$O(n^2)$，但是我跑得很快目前是rank1。代码： #include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; #define N 2010 int f[2][N]; int a[N],b[N],c[N]; inline void maxi(int&x,int y){ if(x<y) x=y; } inline bool cmp(const int&a,const int&b){ return a>b; } int main(){ #ifndef ON ...继续阅读 (45)

题解：要支持在线，还要求区间的和，显然应该用前缀和预处理嘛。但是内存非常鬼畜，50W个long long根本是开不下的！所以应该分块存前缀和，如果从理论上计算的话两个一块内存就够用了，但是这样的话完全没考虑系统的运行空间。所以要留出更多的内存，每16个分成一块就行了。注意开了某些库也会增大内存哦~~代码： #include<cstdio> typedef long long ll; ll p[500020>>4]; int a[500010]; int n,m,t,cnt; ll lastans,l,r; inline ll get(int x){ static ll ans; static int i; ans=p[x>>4]; for(i=((x>>4)<<4)+1;i<=x;++i) ans+=a[i]; return ans; } inline void swap(ll&a,ll&b){ static ll t; t=a; a=b; b=t; } int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #endif scanf("%d%d ...继续阅读 (66)

题解：先说明，这份代码很不幸的超（ka）时（chang）了。借这道题目的机会再重新说明一下后缀自动机&后缀树吧。发现最近一段时间很是习惯于利用后缀树思考问题了，但事实上大概后缀自动机不仅仅是逆序后缀树而已吧。考虑后缀树，定义$siz_i$表示节点$i$的子树內存在多少个结束节点（即后缀）。那么对于每个节点$i$，都实际上对应了$len_i-len_{pa_i}$个字符串，长度是从$len_{pa_i}+1-len_i$连续的。同时这些字符串都会出现$siz_i$次。为了得到这条边上的字符串，我们需要找出这个节点子树内的任意一个后缀的位置，并利用$len_i$以及$len_{pa_i}$来得到这个节点的所有串。考虑一个点的若干条儿子边，边代表的字符串的首字母必定不同，我们用首字母字典序大小来决定遍历顺序的先后。如果想求第$k$小的串，我们就在后缀树上dfs，最终得到是一条边上的第几个串，然后就可以了。后缀自动机是逆序后缀树，自动机体现在后缀树上的trans指针，即支持在一个字符串上在开头添加一个字符得到新的节点的指针。由于是反串的后缀树，那么在开头添加一个字符相当于在原串的末尾添加字符。从根开始，通过若干trans指针会得到一条路径，对于不同字符串，即使路径的最终节点相同，但是路径本身不同。换言之，我们可以将子串的询问问题转化为拓扑图的路径统计问题。上面是随便说的。。。总之， ...继续阅读 (54)

题解:首先答案显然具有单调性，我们考虑二分答案。考虑如果需要让最大的直径$\leq{limit}$，最少需要删掉的边数是多少。我们考虑贪心，从底向上进行考虑，对于一个点作为父亲的情况，考虑所有儿子，将它们按照最长延伸从小到大排序，我们贪心的删掉最长延伸最大的儿子的父亲边直到目前的直径$\leq{limit}$。不过这样为什么是对的呢？有可能在儿子子树里面多删一些边使得儿子的最长延伸减少，不过就算只多删一条边，也只能减小这个儿子在父亲上的排名，在父亲上多删一条边一定比在子树里删边划算。这样大概就可以证明是对的了吧。时间复杂度$O(nlog^2n)$。代码：#include<cstdio> #include<cctype> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> using namespace std; #define N 100010 int head[N],next[N<<1],end[N<<1]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next ...继续阅读 (64)

题解:感觉上暴力好像是卡不掉的，但是我并不知道为什么。感觉有点虚于是预处理了500W的一个表。于是就这样过了。代码:#include<cstdio> #include<cctype> #include<climits> #include<cstdlib> #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long ll; ll f[110]; map<ll,int>M; int c[5000010]; inline int solve(ll x){ int n=upper_bound(f+1,f+89,x)-f; if(x==f[n-1]) return 1; else return min(c[x-f[n-1]],c[f[n]-x])+1; } inline int Solve(ll x){ if(x<=5000000) return c[x]; int n=upper_bound(f+1,f+89,x)-f; if(x==f[n-1]) return 1; else return min(Solve(x-f[n-1] ...继续阅读 (181)

题解:其实很有一些玄学,不知道怎么想到是一个dp问题的。首先肯定要将数组排序,然后令$f[i]$表示前$i$对中至多扔掉几个。那就有转移方程$f[i]=\sum_{j=0}^{i-1}max\{f[j]+calc(j+1,i)\}$。$calc(x,y)$表示从第$x$个到第$y$个至多扔掉几个。我们可以考虑枚举答案判断是否合法。我们考虑能否扔掉$k$个。满足条件当且仅当存在k对两两之间均不能匹配且剩下的存在一种完备匹配。我们贪心的来分配去达成这个条件。怎么贪心呢。。。对于均不能匹配，我们令第$i$小的去匹配第$i$大的.于是就做完了这道题目。但是为什么这样分段是对的呢...我觉得大概就是因为有匹配范围是-1,0,1这个条件吧。我觉得大概不是很容易证明，但是经过了对拍的考验就能出了吧。嗯，我是这样想的。代码:#include<cstdio> #include<cctype> #include<cstdlib> #include<climits> #include<iostream> #include<algorithm> using namespace std; #define N 51 int a[N],f[N]; inline int dis(int a,int b){ return a>b?a- ...继续阅读 (156)

题解:当时A掉的时候其实并不会...于是现在膜别人的题解终于会啦!求方程x^a\equiv{b}\pmod{n}在[0,n-1]内的解的个数.\\我们考虑通过对于两边取指标,转化为线性同余方程问题.\\但是发现n不一定存在原根,我们将n进行质因数分解.\\原方程的解的个数等于每一个子方程x^a\equiv{b}\pmod{p_i^{q_i}}解的个数的乘积.\\我们考虑中国剩余定理,就能发现这样的乘法原理显然成立.\\于是我们只考虑每一个子方程的解的个数.\\我们考虑以下几种情况:\\(1)b存在指标,即(b,p_i)=1\\我们对两边取指标得到a\times{ind(x)}\equiv{ind(b)}\pmod{\phi(p_i^{q_i})}\\由线性同余方程的知识可知,如果(a,\phi(p_i^{q_i}))\not|ind(b),则无解;\\否则解的个数为(a,\phi(p_i^{q_i})).\\(2)b不存在指标,且b=0\\我们可以得到p_i|x,不妨令x=cp_i^{x'}((c,p_i)=1),可以得到ax'\geq{q_i},即x'\geq{\lceil\frac{q_i}{a}\rceil}.\\所以我们有只需满足p_i^{\lceil\frac{q_i}{a}\rceil}|x,于是解的个数就为p_i^{q_i-\lceil\frac{q_i}{a}\rc ...继续阅读 (54)

题解:EXBSGS裸题.代码:#include#include#include#include#include#include#include#includeusing namespace std; typedef long long ll; inline ll gcd(ll a,ll b){ return(!b)?a:gcd(b,a%b); } inline ll pow(ll x,ll y,ll p){ ll re=1,t=x; for(;y;y>>=1,t=t*t%p) if(y&1) re=re*t%p; return re; } inline void exgcd(ll a,ll b,ll&d;,ll&x;,ll&y;){ if(!b){ d=a; x=1; y=0; } else{ exgcd(b,a%b,d,y,x); y-=x*(a/b); } } inline ll inv(ll a,ll p){ ll d,x,y; exgcd(a,p,d,x,y); x=(x%p+p)%p; return x; } struct Ha ...继续阅读 (87)

题解:这题一看一些基本的方法都是不能做的了,再看看时限,果断觉得是分块.然后觉得带一个$log$肯定是死活过不去的.然后我们苦思一下不带$log$的算法.首先分成$O(\sqrt{n})$块,然后$O(n\sqrt{n})$里面算出任意两块之间的答案.然后对于剩下部分,我们用类似于暴力计算的方法一个一个加入当前集合并维护答案就行了.这个可以通过事先记录前缀若干个块每个元素各有多少来高效进行.于是做到了空间时间复杂度均为$O(n\sqrt{n})$.代码:#include#include#include#include#include#include#include#includeusing namespace std; typedef long long ll; #define N 100010 int a[N],b[N],_a[N]; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int get ...继续阅读 (80)

题解:考虑每个数都有一个存在的时间区间.将这个数的存在看做一次区间修改,利用线段树维护打标记即可.(其实和分治的本质是相同的)为了计算插入这个数造成的影响,只需要维护一个线性基即可.详情见代码.代码:#include#include#include#include#include#include#include#include#include#includeusing namespace std; #define N 500010 inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())&&c;!='-'); bool s=c=='-'; int x=s?0:c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return s?-x:x; } #define N 500010 int a[N]; struct Linear ...继续阅读 (103)

题解:首先树上的边权只可能减少.非树边上的权值只可能增大.然后就有对于一条非树边,修改后的权值要不小于所有它覆盖的树边被修改后的权值.注意题目中其实是保证树边数目$\times$非树边数目$\leq{4000}$的.然后对偶一下发现有初始可行解,直接上单纯形.代码:#include#include#include#include#include#includeusing namespace std; #define inf 0x3f3f3f3f struct Linear_Programming{ static const int N=4010; static const int M=1010; int n,m,A[M][N],b[M],c[N],v,B[M],nB[N]; int _c[N],_v,_nB[N],Bins[N+M],nBins[N+M]; inline void pivot(int l,int e){ int i,j; for(i=1;i<=n;++i) if(i!=e) A[l][i]/=A[l][e]; b[l]/=A[l][e]; A[l][e]=1/A[l][e]; for(i= ...继续阅读 (54)

首要思路是构造辅助线性规划,若最优值为0则删除辅助变量得到存在初始可行解线性规划.具体看代码吧.#include#include#include#include#include#includeusing namespace std; #define inf 0x3f3f3f3f struct Linear_Programming{ static const int N=10010; static const int M=1010; int n,m,A[M][N],b[M],c[N],v,B[M],nB[N]; int _c[N],_v,Bins[N+M],nBins[N+M],_nB[N]; inline void pivot(int l,int e){ int i,j; for(i=1;i<=n;++i) if(i!=e) A[l][i]/=A[l][e]; b[l]/=A[l][e]; A[l][e]=1/A[l][e]; for(i=1;i<=m;++i) if(i!=l&&A;[i][e]!=0){ for(j=1;j<=n;++j) ...继续阅读 (40)

题解:事实上$p$是质数...所以我们先求出原根$g$.然后对于两边取指标,就得到$ind(x)\times{k}\equiv{ind(a)}\pmod{p-1}$这就可以直接用拓展欧几里得算法求解了.至于拓展欧几里得的一些细节见代码吧...代码:#include#include#include#include#include#include#include#includeusing namespace std; typedef long long ll; ll pow(ll x,ll y,ll p){ ll re=1,t=x; for(;y;y>>=1,t=t*t%p) if(y&1) re=re*t%p; return re; } inline void exgcd(ll a,ll b,ll&d;,ll&x;,ll&y;){ if(!b){ d=a; x=1; y=0; } else{ exgcd(b,a%b,d,y,x); y-=x*(a/b); } } struct Hashset{ static const int mod=1313131; int head[mod] ...继续阅读 (101)

题解:显然利用最短路求解就行了.代码:#include#include#include#include#include#include#includeusing namespace std; #define inf 0x3f3f3f3f #define mp make_pair typedef pairpii; struct SegmentTree{ pii s[524288]; int M; inline void init(int _siz){ for(M=1;M<(_siz+2);M<<=1); for(int i=1;i<(M<<1);++i) s[i]=mp(inf,0); for(int i=1;i<=_siz;++i) s[M+i].second=i; } inline void upd(int x,int v){ for(s[x+=M].first=v,x>>=1;x;x>>=1) s[x]=min(s[x<<1],s[x<<1^1]); } }Seg; #define N 500010 #define M 2000010 int head[N],next[M],end[M],len[M]; inline void addedge(int a,int b,int c){ static int q=1; end[q ...继续阅读 (145)

题解:(题面有错误,每一次选的并不是与"上一次"选的元素相邻的元素,而是只要与选过的元素相同就可以.)考虑假如我们知道Alice第一个选的元素.那么Alice最大能够拿到的是所有长度为$\lfloor\frac{n+1}{2}\rfloor$且包括这个元素的区间中价值和最小的区间.为什么呢?因为Bob一定可以控制Alice只能拿这个区间.假设$n$是偶数,我们将整个环去掉这段区间,那么完全对称着去取就行了.奇数的情况也是类似.于是利用单调队列处理出所有起点的答案,再取最大值就行了.代码:#include#include#include#include#includeusing namespace std; #define N 500010 int a[N<<1],sum[N<<1],q[N<<1],w[N<<1],fr,ta; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ ...继续阅读 (51)

这个算法是jkxing脑补出来的,ozorzzz...现在我们要求一个最小的$x$满足$a^x\equiv{b}\pmod{c}$.假设满足$(a,c)=1$.不难证明若存在可行解必定有$x ...继续阅读 (44)

题解:这道题没有SPJ...但是http://oj.jdfz.com.cn:8081/oldoj/problem.php?id=1013这里是可以正常提交的...考虑一开始给出的若干有向边,若存在环一定是无解的.否则,我们利用现在的DAG随意得到一个拓扑序列.给剩下的边定向时,我们总是让在序列前面的点指向序列后面的点.这样一定是满足要求的.代码:#include#include#include#include#include#includeusing namespace std; #define N 100010 #define M 100010 int head[N],next[M],end[M],in[N]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q++; ++in[b]; } int q[N],fr,ta,ins[N]; int main(){ int n,m1,m2; cin>>n>>m1>>m2; int a,b,i,j; for(i=1;i<=m1;++i){ scanf("%d%d",&a;,&b;); addedge(a,b) ...继续阅读 (51)