NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #214865 | #2704. Layered Graph | stawalr | 100 | 5543ms | 4860kb | C++ | 3.5kb | 2024-11-22 21:47:26 | 2024-11-22 23:14:02 |
answer
#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int mn=1e6+5,mod=1e9+7;
int n,l,m;
int a[mn],b[mn],c[mn],g[mn];
int d,e,f;
struct mat
{
int a[105][105];
mat(bool f=0)
{
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
a[i][j]=0;
}
}
if(f)
{
for(int i=0;i<m;i++)
{
a[i][i]=1;
}
}
}
mat operator *(mat x)
{
mat res(0);
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
for(int k=0;k<m;k++)
{
res.a[i][j]=(res.a[i][j]+x.a[k][j]*a[i][k])%mod;
}
}
}
return res;
}
};
mat fpow(mat x,int y)
{
mat res(1);
// cerr<<y<<'\n';
// for(int i=0;i<m;i++)
// {
// for(int j=0;j<m;j++)
// {
// cerr<<res.a[i][j]<<" ";
// }
// cerr<<'\n';
// }
while(y)
{
if(y&1)
{
res=res*x;
// for(int i=0;i<m;i++)
// {
// for(int j=0;j<m;j++)
// {
// cerr<<res.a[i][j]<<" ";
// }
// cerr<<'\n';
// }
}
x=x*x;
y>>=1;
// for(int i=0;i<m;i++)
// {
// for(int j=0;j<m;j++)
// {
// cerr<<x.a[i][j]<<" ";
// }
// cerr<<'\n';
// }
// cerr<<"-------\n";
}
return res;
}
void solve()
{
scanf("%lld%lld%lld",&n,&l,&m);
mat x(0);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
// for(int i=0;i<m;i++)
// {
// for(int j=0;j<m;j++)
// {
// cerr<<x.a[i][j]<<" ";
// }
// cerr<<'\n';
// }
for(int i=1;i<=n;i++)
{
scanf("%lld",&b[i]);
g[i]=b[i]%m;
for(int j=0;j<m;j++)
{
x.a[j][(j+b[i])%m]++;
}
}
// for(int i=0;i<m;i++)
// {
// for(int j=0;j<m;j++)
// {
// cerr<<x.a[i][j]<<" ";
// }
// cerr<<'\n';
// }
x=fpow(x,l-2);
// for(int i=0;i<m;i++)
// {
// for(int j=0;j<m;j++)
// {
// cerr<<x.a[i][j]<<" ";
// }
// cerr<<'\n';
// }
for(int i=0;i<m;i++)
{
b[i]=0;
}
for(int i=1;i<=n;i++)
{
b[a[i]%m]++;
// b[i]=0;
// for(int j=0;j<m;j++)
}
// for(int i=0;i<m;i++)
// {
// b[i]=0;
// cerr<<b[i]<<" ";
// }
// cerr<<"\n\n";
for(int i=0;i<m;i++)
{
a[i]=0;
for(int j=0;j<m;j++)
{
a[i]=(a[i]+b[j]*x.a[j][i])%mod;
}
// cerr<<a[i]<<' ';
}
// for(int i=0;i<m;i++)
// {
// b[i]=0;
// }
// for(int i=1;i<=n;i++)
// {
// b[c[i]%m]++;
// }
int ans=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&c[i]);
ans=(ans+a[(2*m-c[i]%m-g[i])%m])%mod;
}
// for(int i=0;i<m;i++)
// {
// ans=(ans+b[i]*a[(2*m-i-g[i])%m])%mod;
// }
printf("%lld\n",ans);
}
signed main()
{
int T;
scanf("%lld",&T);
while(T--)
{
solve();
}
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 27ms
memory: 1736kb
input:
5 100 100 50 32 12 11 9 9 18 31 21 7 6 44 30 18 48 24 11 23 2 45 46 24 14 22 28 18 15 3 10 42 5 41 1...
output:
256484961 688335128 301111418 956880308 113516759
result:
ok 5 lines
Test #2:
score: 5
Accepted
time: 25ms
memory: 1736kb
input:
5 100 100 50 27 42 2 20 37 40 45 34 17 5 6 49 12 35 44 25 12 48 25 2 38 24 16 44 0 45 26 4 0 6 7 47 ...
output:
268228217 575289231 909515477 632982195 407232980
result:
ok 5 lines
Test #3:
score: 5
Accepted
time: 27ms
memory: 1736kb
input:
5 100 100 50 10 2 23 18 49 11 5 18 7 22 33 7 20 9 16 9 25 12 18 19 22 13 2 17 9 12 17 29 19 3 45 20 ...
output:
368262031 447487318 28838623 119822834 460599945
result:
ok 5 lines
Test #4:
score: 5
Accepted
time: 27ms
memory: 1728kb
input:
5 100 100 50 35 28 4 22 33 20 44 41 27 32 30 43 43 30 45 13 35 21 28 47 15 10 18 14 41 23 19 11 23 4...
output:
631584619 328710686 781204767 704656825 306982327
result:
ok 5 lines
Test #5:
score: 5
Accepted
time: 27ms
memory: 1736kb
input:
5 100 100 50 47 10 10 0 35 38 41 29 40 48 32 19 34 3 39 3 4 27 13 7 4 27 32 40 30 29 22 11 29 13 10 ...
output:
88526727 446964081 250214623 430687606 929412854
result:
ok 5 lines
Test #6:
score: 5
Accepted
time: 27ms
memory: 1736kb
input:
5 100 100 50 21 49 36 14 4 38 28 34 36 37 39 29 47 10 15 36 47 43 37 22 35 1 17 27 12 28 14 21 9 42 ...
output:
213489050 162486500 931087617 827492794 278753984
result:
ok 5 lines
Test #7:
score: 5
Accepted
time: 27ms
memory: 1736kb
input:
5 100 100 50 34 31 10 31 39 11 33 41 43 22 7 32 12 8 34 16 15 22 44 49 44 14 47 35 20 37 49 42 19 13...
output:
946958806 267552035 654113271 952182010 169452352
result:
ok 5 lines
Test #8:
score: 5
Accepted
time: 27ms
memory: 1732kb
input:
5 100 100 50 14 18 43 4 22 31 33 34 46 1 4 41 12 5 10 19 20 49 5 31 48 23 46 31 36 26 39 22 20 21 1 ...
output:
458596684 115847030 802032796 115839473 353156511
result:
ok 5 lines
Test #9:
score: 5
Accepted
time: 442ms
memory: 4856kb
input:
5 100000 100000 50 23 34 28 46 34 18 36 20 26 10 12 25 30 41 19 17 26 1 28 35 24 22 10 27 39 42 0 49...
output:
70561313 424223040 792923979 961704079 169991377
result:
ok 5 lines
Test #10:
score: 5
Accepted
time: 434ms
memory: 4860kb
input:
5 100000 100000 50 14 1 21 5 17 40 34 12 40 31 7 42 36 36 0 21 20 25 5 10 19 5 34 39 43 45 5 11 14 2...
output:
994268276 378804580 390197994 95367866 371132199
result:
ok 5 lines
Test #11:
score: 5
Accepted
time: 440ms
memory: 4856kb
input:
5 100000 100000 50 18 48 15 0 26 18 8 33 13 33 33 45 24 12 31 34 38 47 48 43 34 24 28 35 34 10 22 14...
output:
748222759 905960716 623356444 479417704 917976590
result:
ok 5 lines
Test #12:
score: 5
Accepted
time: 438ms
memory: 4860kb
input:
5 100000 100000 50 29 39 33 23 21 22 32 39 49 32 31 23 21 21 45 48 12 31 48 22 33 14 28 5 4 26 33 20...
output:
360713362 166361387 744782134 737025870 955702637
result:
ok 5 lines
Test #13:
score: 5
Accepted
time: 436ms
memory: 4852kb
input:
5 100000 100000 50 3 33 0 45 27 19 16 21 11 46 14 8 8 18 38 24 44 22 34 18 38 41 20 22 11 10 34 24 4...
output:
557420187 821847286 516530302 950637802 21603901
result:
ok 5 lines
Test #14:
score: 5
Accepted
time: 445ms
memory: 4856kb
input:
5 100000 100000 50 41 7 15 45 21 32 10 8 8 2 35 22 45 39 40 39 14 11 44 32 37 8 34 48 49 5 7 42 22 1...
output:
926016839 444197523 600448673 421000185 439008653
result:
ok 5 lines
Test #15:
score: 5
Accepted
time: 439ms
memory: 4856kb
input:
5 100000 100000 50 16 41 15 33 12 46 37 15 33 27 47 8 44 30 33 9 38 2 6 14 42 45 15 20 3 29 27 27 36...
output:
591140332 771565138 751639584 616371864 264496448
result:
ok 5 lines
Test #16:
score: 5
Accepted
time: 441ms
memory: 4860kb
input:
5 100000 100000 50 45 7 6 5 46 1 1 7 35 32 47 12 32 23 39 33 29 14 26 44 21 26 6 13 34 2 19 46 44 20...
output:
643992931 175609322 91025171 148296549 714261495
result:
ok 5 lines
Test #17:
score: 5
Accepted
time: 444ms
memory: 4852kb
input:
5 100000 100000 50 14 6 40 39 26 11 25 8 20 39 42 15 42 47 1 49 32 42 6 30 37 38 47 44 42 38 37 27 1...
output:
693284936 356600861 918845874 96086244 859982327
result:
ok 5 lines
Test #18:
score: 5
Accepted
time: 429ms
memory: 4856kb
input:
5 100000 100000 50 40 33 35 43 48 35 38 43 23 17 41 48 40 8 13 8 31 48 13 29 39 16 38 11 15 42 34 21...
output:
265244724 374891793 239243397 214385292 426456013
result:
ok 5 lines
Test #19:
score: 5
Accepted
time: 464ms
memory: 4856kb
input:
5 100000 100000 50 39 21 5 26 26 38 41 15 33 11 14 42 49 41 38 37 42 1 40 41 37 17 19 29 12 26 13 30...
output:
422422628 389585876 648414157 561977732 63887404
result:
ok 5 lines
Test #20:
score: 5
Accepted
time: 477ms
memory: 4856kb
input:
5 100000 100000 50 28 45 35 35 47 2 9 38 25 34 44 42 4 20 15 28 11 46 21 41 19 46 30 15 49 46 0 35 3...
output:
825400868 872603598 741617494 674186418 305525060
result:
ok 5 lines
