QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#44275#1786. 路径交点myee100 ✓184ms2324kbC++115.3kb2022-08-14 21:02:522022-08-14 21:02:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-14 21:02:54]
  • 评测
  • 测评结果:100
  • 用时:184ms
  • 内存:2324kb
  • [2022-08-14 21:02:52]
  • 提交

answer

// Problem: P7736 [NOI2021] 路径交点
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7736
// Memory Limit: 1 MB
// Time Limit: 1000 ms

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace ConstMod
{
    template<const ullt p>
    class mod_ullt
    {
        private:
            ullt v;
            inline ullt chg(ullt w){return(w<p)?w:w-p;}
            inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
        public:
            mod_ullt():v(0){}
            mod_ullt(ullt v):v(v%p){}
            bol empty(){return!v;}
            inline ullt val(){return v;}
            friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
            friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
            friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
            friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
            friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
            friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
            inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
            inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
            inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
            friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
            friend mod_ullt operator^(mod_ullt a,ullt b){return a._power(b);}
            inline mod_ullt operator-(){return _chg(p-v);}
            mod_ullt sqrt()
            {
                if(power(v,(p-1)>>1,p)!=1)return 0;
                mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
                ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
                mod_ullt x=_power((t+1)>>1),e=_power(t);
                while(k<s)
                {
                    if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
                    e=_power(p-2)*x*x,k++;
                }
                return _min(x,-x),x;
            }
            mod_ullt inv(){return _power(p-2);}
            mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
            voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
            voi print()
            {
                static chr C[20];uint tp=0;
                ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
                while(tp--)putchar(C[tp]);
            }
            voi println(){print(),putchar('\n');}
            mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
        public:
            inline ullt&operator()(){return v;}
            inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
            inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
            inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
            mod_ullt&operator^=(ullt b){return*this=_power(b);}
            mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
            mod_ullt&operator++(){return v=chg(v+1),*this;}
    };
}
typedef ConstMod::mod_ullt<998244353>modint;
typedef std::pair<uint,uint>Pair;
modint A[205][205],Last[205][205];
uint N[205],E[205];
modint det(uint n)
{
	modint ans(1);
	for(uint i=0;i<n;i++)
	{
		{
			uint j=i;
			while(j<n&&!A[j][i]())j++;
			if(j==n)return 0;
			if(i!=j){
				// std::swap(A[i],A[j]);
				for(uint k=0;k<n;k++)
					std::swap(A[i][k],A[j][k]);
				ans=-ans;
			}
		}
		ans*=A[i][i];
		modint v=A[i][i].inv();
		for(uint j=i;j<n;j++)A[i][j]*=v;
		for(uint j=i+1;j<n;j++)
			for(uint k=i+1;k<n;k++)
				A[j][k]-=A[j][i]*A[i][k];
	}
	return ans;
}
int main()
{
    uint t;scanf("%u",&t);
    while(t--)
    {
    	uint k;scanf("%u",&k);
    	for(uint i=0;i<k;i++)scanf("%u",N+i);
    	for(uint i=1;i<k;i++)scanf("%u",E+i);
    	for(uint i=0;i<N[0];i++)for(uint j=0;j<N[0];j++)A[i][j]=i==j;
    	for(uint i=1;i<k;i++)
    	{
    		for(uint p=0;p<N[0];p++)for(uint q=0;q<N[i-1];q++)Last[p][q]=A[p][q];
    		for(uint p=0;p<N[0];p++)for(uint q=0;q<N[i];q++)A[p][q]=0;
    		while(E[i]--)
    		{
    			uint u,v;
    			scanf("%u%u",&u,&v);
    			u--,v--;
    			for(uint p=0;p<N[0];p++)A[p][v]+=Last[p][u];
    		}
    	}
    	// for(uint i=0;i<N[0];i++,putchar('\n'))
	    	// for(uint j=0;j<N[0];j++)
	    		// A[i][j].print(),putchar(' ');
    	det(N[0]).println();
    }
    return 0;
}

詳細信息

Test #1:

score: 5
Accepted
time: 2ms
memory: 2164kb

input:

5
2
10 10
49
1 1
1 2
1 7
1 9
2 3
2 6
2 9
2 10
3 1
3 2
3 3
3 5
3 6
3 7
3 8
3 9
4 2
4 3
4 4
4 7
4 10
5 3
5 7
5 10
6 1
6 2
6 3
6 5
6 8
6 9
7 1
7 3
7 8
7 9
7 10
8 5
8 6
8 7
8 9
9 1
9 3
9 4
9 7
9 10
10 2
10 4
10 6
10 9
10 10
2
10 10
46
1 1
1 2
1 3
1 10
2 1
2 2
2 5
2 9
2 10
3 3
3 7
3 8
4 2
4 5
4 7
4 8
4 1...

output:

998244348
24
21
998244346
6

result:

ok 5 lines

Test #2:

score: 5
Accepted
time: 0ms
memory: 2324kb

input:

5
2
10 10
56
1 1
1 3
1 5
1 7
1 9
1 10
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 3
3 4
3 6
3 8
3 9
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 9
4 10
5 1
5 2
5 5
5 6
5 7
5 10
6 1
6 4
6 5
6 7
7 1
7 3
7 4
8 3
8 4
8 8
9 2
9 3
9 7
9 8
9 10
10 1
10 2
10 6
10 7
10 8
10 9
10 10
2
10 10
48
1 2
1 4
1 5
1 7
1 8
1 9
1 10
2 1
2 3
2 ...

output:

998244350
1
998244334
998244347
998244348

result:

ok 5 lines

Test #3:

score: 5
Accepted
time: 1ms
memory: 2264kb

input:

5
2
10 10
55
1 5
1 6
2 1
2 3
2 4
2 6
2 7
2 8
2 9
2 10
3 3
3 4
3 5
3 6
3 7
3 10
4 1
4 2
4 3
4 4
4 6
4 7
4 8
4 10
5 1
5 2
5 3
5 5
5 7
6 1
6 2
6 4
6 6
7 3
7 5
7 8
7 9
8 1
8 2
8 4
8 6
8 9
8 10
9 1
9 2
9 4
9 6
9 7
10 2
10 3
10 4
10 6
10 8
10 9
10 10
2
10 10
53
1 1
1 4
1 6
1 10
2 1
2 3
2 4
2 6
2 7
2 8
2 9...

output:

5
998244349
1
1
1

result:

ok 5 lines

Test #4:

score: 5
Accepted
time: 2ms
memory: 2308kb

input:

5
2
10 10
53
1 1
1 2
1 5
1 6
1 7
1 10
2 2
2 3
2 8
3 2
3 3
3 5
3 9
3 10
4 1
4 5
4 6
4 7
4 8
4 9
5 1
5 2
5 3
5 5
5 7
5 10
6 5
6 7
6 8
6 9
6 10
7 4
7 6
7 8
7 9
7 10
8 1
8 2
8 5
8 9
9 1
9 2
9 4
9 5
9 10
10 1
10 2
10 3
10 4
10 6
10 7
10 9
10 10
2
10 10
50
1 1
1 4
1 8
1 10
2 3
2 4
2 5
2 7
2 10
3 2
3 3
3 4...

output:

998244343
998244352
998244347
998244343
998244343

result:

ok 5 lines

Test #5:

score: 5
Accepted
time: 0ms
memory: 2244kb

input:

5
10
10 10 10 10 10 10 10 10 10 10
13 10 18 15 18 18 15 14 13
5 4
4 7
9 6
8 9
10 2
2 1
7 8
3 5
6 10
1 3
2 4
5 8
3 8
4 7
7 8
6 10
9 1
2 2
1 4
8 6
5 9
10 3
3 5
7 9
8 2
10 10
1 1
2 4
4 8
6 7
9 5
3 6
5 3
1 4
5 2
10 7
4 10
4 6
2 10
4 2
1 5
9 5
2 6
10 3
1 10
4 2
8 4
7 1
5 8
6 7
3 9
1 9
8 3
5 6
1 4
9 8
5 8...

output:

1
998244352
1
0
998244352

result:

ok 5 lines

Test #6:

score: 5
Accepted
time: 2ms
memory: 2252kb

input:

5
10
10 10 10 10 10 10 10 10 10 10
16 16 14 17 10 12 15 16 13
5 8
1 10
7 2
9 1
6 4
2 7
8 6
3 3
4 9
10 5
5 4
9 6
7 5
1 1
3 5
1 2
8 7
10 6
2 9
1 5
4 3
7 8
6 4
3 10
9 2
5 1
10 5
2 7
4 8
3 3
3 1
4 2
7 7
6 6
9 10
5 5
3 2
8 1
4 3
10 4
2 9
1 8
1 9
4 10
9 2
10 8
7 3
6 10
10 5
5 1
2 4
1 2
3 6
4 8
9 7
8 9
6 9...

output:

1
1
998244352
0
998244352

result:

ok 5 lines

Test #7:

score: 5
Accepted
time: 0ms
memory: 2272kb

input:

5
10
10 10 10 10 10 10 10 10 10 10
55 49 52 51 47 48 58 49 39
1 1
1 3
1 9
2 2
2 3
2 7
2 8
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 8
4 1
4 2
4 3
4 5
4 7
4 9
4 10
5 6
5 9
5 10
6 1
6 5
6 6
6 7
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 10
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 7
9 8
9 9
10 1
10 2
10 3
10 4
10 5
1 1
1 3...

output:

25344
19440
997437953
46080
997544513

result:

ok 5 lines

Test #8:

score: 5
Accepted
time: 1ms
memory: 2324kb

input:

5
10
10 10 10 10 10 10 10 10 10 10
43 48 45 52 50 52 52 46 54
1 1
1 3
1 5
1 6
1 9
1 10
2 1
2 2
2 3
2 5
2 6
2 7
3 5
3 7
3 8
4 3
4 4
4 5
4 7
4 9
5 1
5 2
5 5
5 7
5 10
6 2
6 3
6 6
6 8
7 10
8 1
8 2
8 3
8 6
8 9
9 1
9 4
9 5
9 9
10 1
10 6
10 7
10 8
1 1
1 2
1 4
1 7
2 1
2 2
2 7
2 8
2 9
3 2
3 3
3 4
3 5
3 6
3 8...

output:

998237441
998050817
1920
138240
998239553

result:

ok 5 lines

Test #9:

score: 5
Accepted
time: 2ms
memory: 2248kb

input:

5
10
10 13 10 13 10 10 12 11 11 10
58 62 62 64 49 55 62 57 51
1 2
1 5
1 6
1 9
2 7
2 10
2 11
2 12
2 13
3 4
3 5
3 8
3 9
3 11
3 12
4 2
4 3
4 7
4 11
4 12
5 2
5 4
5 6
5 7
5 8
5 10
5 11
5 13
6 4
6 5
6 6
6 7
6 8
6 10
6 11
6 12
7 2
7 4
7 6
7 8
7 9
7 12
7 13
8 1
8 2
8 6
8 7
8 9
8 10
8 12
9 4
9 6
9 8
9 13
10 ...

output:

0
431535363
869602600
0
462374665

result:

ok 5 lines

Test #10:

score: 5
Accepted
time: 2ms
memory: 2268kb

input:

5
10
10 14 11 10 10 13 10 13 10 10
66 75 55 45 66 53 60 66 56
1 1
1 5
1 7
1 9
2 2
2 5
2 6
2 10
2 12
3 1
3 6
3 7
3 12
3 14
4 3
4 4
4 5
4 7
4 10
4 12
4 13
4 14
5 3
5 5
5 11
5 12
5 13
5 14
6 3
6 4
6 6
6 8
6 9
6 13
6 14
7 1
7 3
7 4
7 6
7 7
7 9
7 12
7 13
7 14
8 1
8 2
8 3
8 7
8 8
8 9
8 10
8 11
8 12
9 1
9 ...

output:

509445037
210531260
116561285
0
480038571

result:

ok 5 lines

Test #11:

score: 5
Accepted
time: 0ms
memory: 2164kb

input:

5
2
10 10
56
1 1
1 2
1 3
1 5
1 6
1 7
1 9
2 1
2 3
2 5
2 7
2 9
3 2
3 3
3 4
3 8
3 10
4 1
4 2
4 5
4 6
5 1
5 2
5 3
5 4
5 7
5 8
5 10
6 1
6 2
6 3
6 7
7 1
7 3
7 4
7 5
7 6
7 7
7 8
8 1
8 2
8 3
8 4
8 5
8 7
9 2
9 4
9 8
9 9
10 1
10 2
10 3
10 4
10 7
10 9
10 10
2
10 10
46
1 1
1 2
1 3
1 5
1 7
1 9
2 2
2 7
2 8
2 9
3 ...

output:

998244347
7
547857492
998244348
998244349

result:

ok 5 lines

Test #12:

score: 5
Accepted
time: 3ms
memory: 2164kb

input:

5
2
10 10
42
1 1
1 4
1 5
1 7
1 8
2 1
2 2
2 8
3 1
3 5
3 6
3 8
4 3
4 5
5 1
5 3
5 4
5 7
5 9
5 10
6 2
6 6
6 8
7 1
7 3
7 4
7 10
8 3
8 4
8 8
8 10
9 3
9 5
9 7
9 8
9 10
10 2
10 4
10 5
10 6
10 8
10 9
2
100 100
4905
1 1
1 2
1 5
1 6
1 7
1 10
1 13
1 14
1 15
1 17
1 18
1 20
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 32...

output:

998244341
530973746
2
0
1

result:

ok 5 lines

Test #13:

score: 5
Accepted
time: 1ms
memory: 2252kb

input:

5
2
10 10
58
1 1
1 2
1 4
1 9
1 10
2 2
2 3
2 6
2 7
2 8
3 3
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 5
4 6
4 7
4 8
5 1
5 2
5 3
5 4
5 5
5 7
5 8
5 9
5 10
6 1
6 2
6 5
6 6
6 7
6 9
7 3
7 4
7 5
7 6
7 7
7 8
7 10
8 1
8 4
8 5
8 9
8 10
9 2
9 5
9 8
9 9
9 10
10 2
10 6
10 7
10 8
2
10 10
55
1 1
1 5
1 7
1 8
1 10
2 1
2 2
2 4
2...

output:

3
998244351
998244348
2
741330205

result:

ok 5 lines

Test #14:

score: 5
Accepted
time: 7ms
memory: 2320kb

input:

5
100
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

1
998244352
1
0
1

result:

ok 5 lines

Test #15:

score: 5
Accepted
time: 6ms
memory: 2268kb

input:

5
100
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

0
1
998244352
1
998244352

result:

ok 5 lines

Test #16:

score: 5
Accepted
time: 123ms
memory: 2256kb

input:

5
100
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

334543195
834743238
64906936
887345970
749415036

result:

ok 5 lines

Test #17:

score: 5
Accepted
time: 114ms
memory: 2308kb

input:

5
100
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

551005664
774916190
258165927
333831611
45511363

result:

ok 5 lines

Test #18:

score: 5
Accepted
time: 177ms
memory: 2256kb

input:

5
100
10 15 13 13 12 13 13 13 10 13 11 11 11 12 11 12 13 11 12 13 10 10 10 11 11 12 12 10 10 10 11 10 12 12 10 13 12 12 12 11 10 12 13 12 13 13 12 10 10 11 10 12 10 10 10 12 11 12 12 10 12 12 11 15 13 12 10 11 12 12 10 11 11 10 10 12 11 12 13 13 10 13 13 13 10 11 11 11 12 10 11 13 10 12 10 10 13 11 ...

output:

0
131476393
674791629
0
453887582

result:

ok 5 lines

Test #19:

score: 5
Accepted
time: 177ms
memory: 2268kb

input:

5
100
10 12 10 13 10 12 13 12 12 13 10 11 13 12 13 12 10 12 13 12 10 12 12 12 10 10 13 12 10 10 13 11 10 12 11 12 10 10 13 11 11 11 12 10 11 11 11 13 13 13 13 11 11 12 10 10 13 13 10 11 13 11 11 15 10 10 13 11 12 12 13 10 11 13 12 13 11 10 11 10 13 13 10 10 13 11 13 13 10 13 12 13 13 11 13 11 11 12 ...

output:

0
654380406
500344548
0
452282079

result:

ok 5 lines

Test #20:

score: 5
Accepted
time: 184ms
memory: 2244kb

input:

5
100
100 119 112 115 121 120 115 112 137 116 150 123 115 113 112 113 130 118 104 127 103 122 123 118 116 139 102 117 137 111 131 135 106 119 135 106 119 103 115 124 123 135 135 122 134 117 106 128 115 121 115 115 131 112 124 135 120 113 174 113 106 115 101 124 101 117 126 130 113 105 124 139 129 12...

output:

50989987
555456312
817057040
0
277357563

result:

ok 5 lines

Extra Test:

score: 0
Extra Test Passed