QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#296296 | #7775. 【模板】矩阵快速幂 | zhouhuanyi | 0 | 189ms | 12792kb | C++14 | 4.6kb | 2024-01-02 18:01:45 | 2024-01-02 18:01:46 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define M 180000
#define N 300
#define mod 998244353
using namespace std;
const __int128 INF=(__int128)(1e32);
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
struct reads
{
int num;
long long data;
};
int S,T,n,m,tk,inv[N+1],md[N+1],num[M+1][N+1];
__int128 DP[N+1][N+1],DSP[N+1][N+1],sk;
string k;
vector<reads>E[N+1];
struct frac
{
__int128 x;
int y;
bool operator < (const frac &t)const
{
return x*t.y<y*t.x;
}
bool operator >= (const frac &t)const
{
return x*t.y>=y*t.x;
}
bool operator == (const frac &t)const
{
return x*t.y==y*t.x;
}
bool operator != (const frac &t)const
{
return x*t.y!=y*t.x;
}
};
frac operator + (frac a,frac b)
{
return (frac){a.x*b.y+a.y*b.x,a.y*b.y};
}
frac operator - (frac a,frac b)
{
return (frac){a.x*b.y-a.y*b.x,a.y*b.y};
}
struct rds
{
frac a,b;
bool operator < (const rds &t)const
{
return a!=t.a?a<t.a:b<t.b;
}
bool operator == (const rds &t)const
{
return a==t.a&&b==t.b;
}
bool operator != (const rds &t)const
{
return a!=t.a||b!=t.b;
}
};
rds zero=(rds){(frac){0,1},(frac){0,1}},inf=(rds){(frac){1,0},(frac){1,0}},dp[2][N+1],delta[N+1][N+1];
rds operator + (rds x,rds y)
{
if (x==inf||y==inf) return inf;
x.a=x.a+y.a,x.b=x.b+y.b;
if (x.b>=(frac){sk,1}) x.a=x.a+(frac){1,1},x.b=x.b-(frac){sk,1};
return x;
}
rds operator - (rds x,rds y)
{
if (x==inf) return inf;
x.a=x.a-y.a,x.b=x.b-y.b;
if (x.b<(frac){0,1}) x.a=x.a-(frac){1,1},x.b=x.b+(frac){sk,1};
return x;
}
rds change(rds x)
{
__int128 d;
if (x.b.x>=0) d=x.b.x/x.b.y/sk,x.a=x.a+(frac){d,1},x.b=x.b-(frac){d*sk,1};
else d=(-x.b.x+x.b.y*sk-1)/x.b.y/sk,x.a=x.a-(frac){d,1},x.b=x.b+(frac){d*sk,1};
return x;
}
int get(rds x)
{
if (x==inf) return -1;
__int128 res=(x.a.x%mod)*inv[x.a.y]*tk+(x.b.x%mod)*inv[x.b.y];
res=MD2(res%mod);
return res;
}
int main()
{
int x,y,d,op;
long long z;
inv[1]=1;
for (int i=2;i<=N;++i) inv[i]=MD2(-1ll*(mod/i)*inv[mod%i]%mod);
S=read(),T=read();
for (int qt=1;qt<=T;++qt)
{
n=read(),m=read(),sk=tk=0,cin>>k;
for (int i=2;i<=n;++i) md[i]=0;
for (int i=1;i<=n;++i) E[i].clear();
for (int i=0;i<k.length();++i)
{
sk=min(sk*10+k[i]-'0',INF),tk=(tk*10ll+k[i]-'0')%mod;
for (int j=2;j<=n;++j) md[j]=(md[j]*10ll+k[i]-'0')%j;
}
for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),E[x].push_back((reads){y,z});
for (int i=1;i<=n;++i)
{
for (int j=0;j<=n;++j)
for (int k=1;k<=n;++k)
DSP[j][k]=INF;
DSP[0][i]=0;
for (int j=1;j<=n;++j)
for (int k=1;k<=n;++k)
for (int t=0;t<E[k].size();++t)
DSP[j][E[k][t].num]=min(DSP[j][E[k][t].num],DSP[j-1][k]+E[k][t].data);
for (int j=0;j<=n;++j) DP[j][i]=DSP[j][i];
}
for (int i=1;i<=n;++i)
for (int j=n*n-i+1;j<=n*n;++j)
num[i][j%i]=j;
if (sk<=((n*n)<<1))
{
for (int i=1;i<=n;++i) dp[0][i]=inf;
dp[0][1]=zero,op=0;
for (int i=1;i<=sk;++i)
{
op^=1;
for (int j=1;j<=n;++j) dp[op][j]=inf;
for (int j=1;j<=n;++j)
for (int k=0;k<E[j].size();++k)
dp[op][E[j][k].num]=min(dp[op][E[j][k].num],dp[op^1][j]+change((rds){(frac){0,1},(frac){E[j][k].data,1}}));
}
for (int i=1;i<=n;++i) printf("%d ",get(dp[op][i]));
puts("");
}
else
{
for (int i=0;i<n;++i)
for (int j=1;j<=n;++j)
delta[i][j]=inf;
dp[0][1]=zero,op=0;
for (int i=1;i<=n*n;++i)
{
op^=1;
for (int j=1;j<=n;++j) dp[op][j]=inf;
for (int j=1;j<=n;++j)
for (int k=0;k<E[j].size();++k)
dp[op][E[j][k].num]=min(dp[op][E[j][k].num],dp[op^1][j]+change((rds){(frac){0,1},(frac){E[j][k].data,1}}));
if (i>=n*n-n+1)
{
for (int j=1;j<=n;++j)
if (dp[op][j]!=inf)
{
for (int k=2;k<=n;++k)
if (DP[k][j]!=INF)
d=num[k][((md[k]-i)%k+k)%k],delta[n*n-d][j]=min(delta[n*n-d][j],dp[op][j]+change((rds){(frac){DP[k][j],k},(frac){-DP[k][j]*(d+i),k}}));
}
}
}
op=0;
for (int i=1;i<=n;++i) dp[op][i]=delta[0][i];
for (int i=n*n-1;i>=0;--i)
{
op^=1;
for (int j=1;j<=n;++j) dp[op][j]=inf;
if (i>=n*n-n+1)
{
for (int j=1;j<=n;++j) dp[op][j]=delta[n*n-i][j];
}
for (int j=1;j<=n;++j)
for (int k=0;k<E[j].size();++k)
dp[op][E[j][k].num]=min(dp[op][E[j][k].num],dp[op^1][j]+change((rds){(frac){0,1},(frac){E[j][k].data,1}}));
}
for (int i=1;i<=n;++i) printf("%d ",get(dp[op][i]));
puts("");
}
}
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 10
Accepted
time: 77ms
memory: 11980kb
input:
1 1 100 101 899539897889989959 74 35 910832669819965536 35 85 910832669819965536 85 88 910832669819965536 88 30 910832669819965536 30 58 910832669819965536 58 60 910832669819965536 60 34 910832669819965536 34 8 910832669819965536 8 67 910832669819965536 67 89 910832669819965536 89 32 910832669819965...
output:
395495792 395495781 395495783 395495839 395495793 395495789 395495754 395495832 395495845 395495755 395495823 395495773 395495753 395495800 395495782 395495763 395495847 395495761 395495794 395495791 395495786 395495821 395495798 395495765 395495772 395495770 395495757 395495819 395495843 395495828 ...
result:
ok 100 numbers
Test #2:
score: 0
Accepted
time: 182ms
memory: 12792kb
input:
1 1 100 200 998858598565699977 89 61 596014036562538539 89 84 921297646113897322 61 84 946923234442637386 61 35 641628261157284465 84 35 979893473772327497 84 78 700172488379560611 35 78 963617193748189613 35 54 951598888254521423 78 54 680825215292116806 78 21 737055858973038555 54 21 7491794406112...
output:
590375247 265938345 203065828 597548045 369717762 226160283 377877020 360218254 956162456 408060901 387231165 759578975 67601808 790211315 608425007 343195480 177353482 436533546 717630459 417099733 542227025 861764246 913806375 587268602 989846681 435016550 66609901 817090566 256847656 844441854 94...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 185ms
memory: 10456kb
input:
1 1 100 181 348568663892999968 25 19 990622898175774733 19 94 871060999389241529 94 24 969317630558501400 24 43 908457844888427461 43 52 816088481082287266 52 62 978618931332609685 62 99 761714433396732044 99 85 741344935503895668 85 64 964684335126604843 64 69 988098065125373655 69 31 7506975506815...
output:
916998469 916998469 916998469 76035207 62461893 916998469 389136594 916998469 916998469 173423529 164423356 822964468 626456020 916998469 744111524 916998469 398953850 916998469 342238577 916998469 255074799 784015663 916998469 740933556 587088671 811719512 916998469 916998469 916998469 916998469 14...
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 189ms
memory: 10356kb
input:
1 1 100 189 295064635124730243 18 50 754672892083203214 50 88 962632394366987404 88 15 906700334097319336 15 26 967741400981618572 26 91 996214498763867892 91 35 882157548994344280 35 68 983621159612138407 68 51 563935036482744182 51 75 991205513962219551 75 72 974025375183814852 72 11 7979447663592...
output:
663199381 739882534 663199381 28600701 663199381 944601671 836329160 894091561 629507606 663199381 246830507 663199381 491987421 663199381 802123884 663199381 663199381 663199381 414785533 989396289 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 4...
result:
ok 100 numbers
Test #5:
score: -10
Runtime Error
input:
1 254 40 74 997173688939799978 38 6 890721839505665075 6 10 992308491267087930 10 29 960202932780090595 29 20 952827125924298715 20 34 868314670055961466 34 31 756448635709788087 31 14 857625921909632516 14 18 917667459973696862 18 21 985939328882662624 21 1 734882468602343649 1 11 66102593854575036...
output:
177014577 177014577 177014577 885341552 472856470 177014577 363547548 177014577 499847464 653076748 177014577 177014577 177014577 177014577 487939796 177014577 213466543 586729345 244952763 177014577 177014577 177014577 177014577 890105934 177014577 177014577 890105934 177014577 177014577 798890006 ...
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #7:
score: 0
Time Limit Exceeded
input:
2 1 300 598 8179377797889487867988994778539839593376697796496698959964978969 1 2 977880533270721156 2 1 977880533270721156 2 3 977880533270721156 3 2 977880533270721156 3 4 977880533270721156 4 3 977880533270721156 4 5 977880533270721156 5 4 977880533270721156 5 6 977880533270721156 6 5 977880533270...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #3:
0%