QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #540819 | #8134. LCA Counting | PhantomThreshold# | WA | 1ms | 3676kb | C++20 | 18.7kb | 2024-08-31 17:54:56 | 2024-08-31 17:54:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace gauss{
typedef long long ll;
const ll mod=998244353;
ll ksm(ll a,ll x){
ll ret=1;
for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
return ret;
}
ll inv(ll a){return ksm(a,mod-2);}
ll zero=0;
ll one=1;
ll a[433][433],ans[433];
void gauss(int ROW,int COLUMN){
int m=COLUMN,r=1;
int n=ROW;
for (int i=1;i<=m && r<=n;i++){
ll maxx=zero;
int maxp=r;
for (int j=r;j<=n;j++){
if (a[j][i]!=zero){
maxx=a[j][i],maxp=j;
break;
}
}
if (maxx==zero) continue;
for (int j=i;j<=m;j++) swap(a[r][j],a[maxp][j]);
for (int j=r+1;j<=n;j++){
ll t=a[j][i]*inv(a[r][i])%mod;
for (int k=i;k<=m;k++){
a[j][k]=(a[j][k]-t*a[r][k]%mod+mod)%mod;
}
}
r++;
}
for (int i=n;i>=1;i--){
for (int j=1;j<=m;j++){
if (a[i][j]!=zero){
ll t=a[i][j];
ll invt=inv(t);
for (int l=j;l<=m;l++) a[i][l]=a[i][l]*invt%mod;
for (int k=i-1;k>=1;k--){
ll tmp=a[k][j];
for (int l=j;l<=m;l++)
a[k][l]=(a[k][l]-tmp*a[i][l]%mod+mod)%mod;
}
break;
}
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<m;j++){
if (a[i][j]!=zero){
ans[j]=a[i][m];
break;
}
}
}
}
}
typedef long long ll;
const ll mod=998244353;
long long c[550];
int main(){
ios_base::sync_with_stdio(false);
int TC=1;
cin >> TC;
for (;TC--;){
long long n,m;
cin >> n >> m;
for (int i=1;i<=m;i++){
long long u,v;
cin >> u >> v >> c[i];
gauss::a[i][i]=1;
gauss::a[i][m+u]=1;
gauss::a[i][m+v]=mod-1;
gauss::a[m+u][i]=1;
gauss::a[m+v][i]=mod-1;
}
gauss::a[m+1][m+n+1]=1;
for (int i=1;i<=m+n+1;i++) gauss::a[m+n][i]=0;
gauss::a[m+n][m+n]=1;
cerr << "------------" << endl;
for (int i=1;i<=n+m;i++){
for (int j=1;j<=n+m+1;j++){
cerr << setw(10) << gauss::a[i][j] << " ";
}
cerr << endl;
}
cerr << "----------" << endl;
gauss::gauss(n+m,n+m+1);
cerr << "------------" << endl;
for (int i=1;i<=n+m;i++){
for (int j=1;j<=n+m+1;j++){
cerr << setw(10) << gauss::a[i][j] << " ";
}
cerr << endl;
}
cerr << "ans : ";
for (int i=1;i<=n+m;i++) cerr << gauss::ans[i] << " ";
cerr << endl;
cerr << "----------" << endl;
ll ans=0;
for (int i=1;i<=m;i++) ans=(ans+c[i]*gauss::ans[i]%mod*gauss::ans[i]%mod)%mod;
cout << ans << "\n";
for (int i=1;i<=n+m+1;i++){
gauss::ans[i]=0;
for (int j=1;j<=n+m+1;j++){
gauss::a[i][j]=0;
}
}
}
return 0;
}
/*
4
4 4
1 2 1
2 4 1
1 3 1
3 4 1
------------
1 0 0 0 1 998244352 0 0 0
0 1 0 0 0 1 0 998244352 0
0 0 1 0 1 0 998244352 0 0
0 0 0 1 0 0 1 998244352 0
1 0 1 0 0 0 0 0 1
998244352 1 0 0 0 0 0 0 0
0 0 998244352 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0
----------
------------
1 0 0 0 499122178 415935145 506054429 0 537249565
0 1 0 0 0 665496237 942786333 0 693225245
0 0 1 0 499122178 83187029 201035319 0 856133178
0 0 0 1 0 0 249561090 0 374341632
0 0 0 0 1 166374058 901192818 0 464460914
0 0 0 0 0 1 915057323 0 540715691
0 0 0 0 0 0 1 0 499122176
0 0 0 0 0 0 0 1 0
ans : 537249565 693225245 856133178 374341632 464460914 540715691 499122176 0
----------
811145748
3 3
1 2 1
1 3 1
2 3 1
------------
1 0 0 1 998244352 0 0
0 1 0 1 0 998244352 0
0 0 1 0 1 998244352 0
1 1 0 0 0 0 1
998244352 0 1 0 0 0 0
0 0 0 0 0 1 0
----------
------------
1 0 0 499122178 415935145 0 859599304
0 1 0 499122178 83187029 0 970515343
0 0 1 0 665496237 0 110916039
0 0 0 1 166374058 0 942786333
0 0 0 0 1 0 665496235
0 0 0 0 0 1 0
ans : 859599304 970515343 110916039 942786333 665496235 0
----------
392827639
5 6
1 2 1
2 3 3
2 4 1
3 4 1
3 5 1
1 5 8
------------
1 0 0 0 0 0 1 998244352 0 0 0 0
0 1 0 0 0 0 0 1 998244352 0 0 0
0 0 1 0 0 0 0 1 0 998244352 0 0
0 0 0 1 0 0 0 0 1 998244352 0 0
0 0 0 0 1 0 0 0 1 0 998244352 0
0 0 0 0 0 1 1 0 0 0 998244352 0
1 0 0 0 0 1 0 0 0 0 0 1
998244352 1 1 0 0 0 0 0 0 0 0 0
0 998244352 0 1 1 0 0 0 0 0 0 0
0 0 998244352 998244352 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
----------
------------
1 0 0 0 0 0 499122178 748683263 61430422 451384725 0 386290640
0 1 0 0 0 0 0 199648872 841596776 921198576 0 615235632
0 0 1 0 0 0 0 199648872 150504533 92639651 0 379013596
0 0 0 1 0 0 0 0 307152110 169685428 0 762022317
0 0 0 0 1 0 0 0 307152110 714182350 0 473273950
0 0 0 0 0 1 499122178 948332135 211934955 90276945 0 476555869
0 0 0 0 0 0 1 898419917 423869910 180553890 0 953111738
0 0 0 0 0 0 0 1 875383509 95474903 0 724785249
0 0 0 0 0 0 0 0 1 858629757 0 232267917
0 0 0 0 0 0 0 0 0 1 0 907494866
0 0 0 0 0 0 0 0 0 0 1 0
ans : 386290640 615235632 379013596 762022317 473273950 476555869 953111738 724785249 232267917 907494866 0
----------
293750696
4 5
1 2 1
1 3 2
2 3 1
3 4 1
4 2 8
------------
1 0 0 0 0 1 998244352 0 0 0
0 1 0 0 0 1 0 998244352 0 0
0 0 1 0 0 0 1 998244352 0 0
0 0 0 1 0 0 0 1 998244352 0
0 0 0 0 1 0 998244352 0 1 0
1 1 0 0 0 0 0 0 0 1
998244352 0 1 0 998244352 0 0 0 0 0
0 998244352 998244352 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
----------
------------
1 0 0 0 0 499122178 748683263 118541517 0 564631962
0 1 0 0 0 499122178 948332135 373093825 0 337531372
0 0 1 0 0 0 199648872 254552308 0 771143763
0 0 0 1 0 0 0 374341634 0 311951360
0 0 0 0 1 0 798595481 369350411 0 913393583
0 0 0 0 0 1 898419917 496626565 0 300721111
0 0 0 0 0 0 1 573990502 0 212126925
0 0 0 0 0 0 0 1 0 499122176
0 0 0 0 0 0 0 0 1 0
ans : 564631962 337531372 771143763 311951360 913393583 300721111 212126925 499122176 0
----------
476660509
E:\code>g++ H.cpp -o H
E:\code>clrscr
'clrscr' 不是内部或外部命令，也不是可运行的程序
或批处理文件。
E:\code>H
4
4 4
1 2 1
2 4 1
1 3 1
3 4 1
------------
1 0 0 0 1 998244352 0 0 0
0 1 0 0 0 1 0 998244352 0
0 0 1 0 1 0 998244352 0 0
0 0 0 1 0 0 1 998244352 0
1 0 1 0 0 0 0 0 1
998244352 1 0 0 0 0 0 0 0
0 0 998244352 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0
----------
------------
1 0 0 0 0 0 0 0 499122177
0 1 0 0 0 0 0 0 499122177
0 0 1 0 0 0 0 0 499122177
0 0 0 1 0 0 0 0 499122177
0 0 0 0 1 0 0 0 998244352
0 0 0 0 0 1 0 0 499122176
0 0 0 0 0 0 1 0 499122176
0 0 0 0 0 0 0 1 0
ans : 499122177 499122177 499122177 499122177 998244352 499122176 499122176 0
----------
1
3 3
1 2 1
1 3 1
2 3 1
------------
1 0 0 1 998244352 0 0
0 1 0 1 0 998244352 0
0 0 1 0 1 998244352 0
1 1 0 0 0 0 1
998244352 0 1 0 0 0 0
0 0 0 0 0 1 0
----------
------------
1 0 0 0 0 0 332748118
0 1 0 0 0 0 665496236
0 0 1 0 0 0 332748118
0 0 0 1 0 0 332748117
0 0 0 0 1 0 665496235
0 0 0 0 0 1 0
ans : 332748118 665496236 332748118 332748117 665496235 0
----------
665496236
5 6
1 2 1
2 3 3
2 4 1
3 4 1
3 5 1
1 5 8
------------
1 0 0 0 0 0 1 998244352 0 0 0 0
0 1 0 0 0 0 0 1 998244352 0 0 0
0 0 1 0 0 0 0 1 0 998244352 0 0
0 0 0 1 0 0 0 0 1 998244352 0 0
0 0 0 0 1 0 0 0 1 0 998244352 0
0 0 0 0 0 1 1 0 0 0 998244352 0
1 0 0 0 0 1 0 0 0 0 0 1
998244352 1 1 0 0 0 0 0 0 0 0 0
0 998244352 0 1 1 0 0 0 0 0 0 0
0 0 998244352 998244352 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0
----------
------------
1 0 0 0 0 0 0 0 0 0 0 816745380
0 1 0 0 0 0 0 0 0 0 0 544496920
0 0 1 0 0 0 0 0 0 0 0 272248460
0 0 0 1 0 0 0 0 0 0 0 725995893
0 0 0 0 1 0 0 0 0 0 0 816745380
0 0 0 0 0 1 0 0 0 0 0 181498974
0 0 0 0 0 0 1 0 0 0 0 816745379
0 0 0 0 0 0 0 1 0 0 0 635246406
0 0 0 0 0 0 0 0 1 0 0 181498973
0 0 0 0 0 0 0 0 0 1 0 907494866
0 0 0 0 0 0 0 0 0 0 1 0
ans : 816745380 544496920 272248460 725995893 816745380 181498974 816745379 635246406 181498973 907494866 0
----------
486747251
4 5
1 2 1
1 3 2
2 3 1
3 4 1
4 2 8
------------
1 0 0 0 0 1 998244352 0 0 0
0 1 0 0 0 1 0 998244352 0 0
0 0 1 0 0 0 1 998244352 0 0
0 0 0 1 0 0 0 1 998244352 0
0 0 0 0 1 0 998244352 0 1 0
1 1 0 0 0 0 0 0 0 1
998244352 0 1 0 998244352 0 0 0 0 0
0 998244352 998244352 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
----------
------------
1 0 0 0 0 0 0 0 0 499122177
0 1 0 0 0 0 0 0 0 499122177
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 499122177
0 0 0 0 1 0 0 0 0 499122176
0 0 0 0 0 1 0 0 0 998244352
0 0 0 0 0 0 1 0 0 499122176
0 0 0 0 0 0 0 1 0 499122176
0 0 0 0 0 0 0 0 1 0
ans : 499122177 499122177 0 499122177 499122176 998244352 499122176 499122176 0
----------
3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3676kb
input:
7 1 1 2 4 2 2
output:
2 0 0 0 0 0 0
result:
wrong answer 1st numbers differ - expected: '1', found: '2'