QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#44275 | #1786. 路径交点 | myee | 100 ✓ | 184ms | 2324kb | C++11 | 5.3kb | 2022-08-14 21:02:52 | 2022-08-14 21:02:54 |
Judging History
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