思路：矩乘优化DP

提交：3次（用了一个奇怪的东西导致常数过大）

题解：

如果可以走完正向边后又走反向边那就显然了，但是不能走，所以我们要将正反向边分别编号，区分正反向边。

所以这道题的矩阵是以边的编号（边的邻接矩阵），而非点来DP的。

具体地，记录每个边$w_i=(u_i,v_i)$和$w_{i^1}=(v_{i^1},u_{i^1})$,注意这个有向的。

设起点为$s$,终点为$t$，我们的初始矩阵$S$是一根行向量，把所有的$w_i \ and \ u_i==s $设为$1$，表示$s$与$w_i$连通;

然后转移矩阵$a$：若$v_i==u_j \ and \ i!=j \ xor \ 1$ ,即两条边相连，但不是互为正反向边，则在边的邻接矩阵中设为$1$。

然后快速幂，并令$ans=S*a$

最后求解答案时，统计所有$ans$中$w_i \ and \ v_i==t$ 的答案，即为最终的答案。

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define R register int#define ull unsigned long long#define ll long long#define pause (for(R i=1;i<=10000000000;++i))#define In freopen("NOIPAK++.in","r",stdin)#define Out freopen("out.out","w",stdout)namespace Fread {static char B[1<<15],*S=B,*D=B;#ifndef JACK#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)#endifinline int g() {    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;} inline bool isempty(const char& ch) {
   return (ch<=36||ch>=127);}inline void gs(char* s) {    register char ch; while(isempty(ch=getchar()));    do *s++=ch; while(!isempty(ch=getchar()));}} using Fread::g; using Fread::gs;namespace Luitaryi {const int N=100010;int n,m,T;int pos[N],l[1300],r[1300];double a[N];struct STK {    double stk[1300]; int top;    inline int calc(double x) {        R l=1,r=top+1;        while(l
        
         >1;            if(stk[md]<=x) l=md+1; else r=md;        }         return top+1-l;    }}s[1300];inline void main() {    n=g(),m=g(); T=sqrt(n*log2(n));     for(R i=1;i<=n;++i) pos[i]=(i-1)/T+1;    for(R i=1,lim=pos[n];i<=lim;++i) l[i]=(i-1)*T+1;    for(R i=1,lim=pos[n];i
        
       
      
     

---

2019.07.20