NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #204838 | #3630. 数列操作 | drdilyor | 100 | 7665ms | 4148kb | C++ | 1.7kb | 2024-06-10 09:37:02 | 2024-06-10 12:02:13 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;
const int mod=1e9+7;
#define Matrix vector<vector<int> >
Matrix mul(Matrix a,Matrix b){
Matrix res((int)a.size());
for(int i=0;i<(int)a.size();i++){res[i].resize((int)b[0].size());}
for(int k=0;k<(int)a[0].size();k++){
for(int i=0;i<(int)a.size();i++){
for(int j=0;j<(int)b[0].size();j++)res[i][j]+=a[i][k]*b[k][j]%mod,res[i][j]%=mod;
}
}
return res;
}
Matrix I(){
Matrix res(n);
for(int i=0;i<n;i++)res[i].resize(n),res[i][i]=1;
return res;
}
Matrix qkp(Matrix a,int k){
Matrix res=I();
while(k){
if(k&1)res=mul(res,a);
k/=2;
a=mul(a,a);
}
return res;
}
Matrix bs[31];
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>q;
Matrix trans=I();
for(int i=1;i<=m;i++){
string s;
int o,p;cin>>s>>o>>p;o--,p--;
if(s=="swap"){
for(int j=0;j<n;j++)swap(trans[j][o],trans[j][p]);
}
else{
for(int j=0;j<n;j++){
trans[j][o]+=trans[j][p];
if(trans[j][o]>=mod)trans[j][o]-=mod;
}
}
}
//2 1 1
//2 1 3
bs[0]=trans;
for(int i=1;i<=30;i++)bs[i]=mul(bs[i-1],bs[i-1]);
while(q--){
Matrix f(1);f[0].resize(n);
for(int i=0;i<n;i++)cin>>f[0][i];
int k;cin>>k;
for(int i=0;i<=30;i++){
if(k&(1<<i))f=mul(f,bs[i]);
}
for(int i=0;i<n;i++)cout<<f[0][i]<<" ";
cout<<"\n";
}
//a[1] a[2] a[3]
//1
// 1
// 1
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 4ms
memory: 1564kb
input:
30 30 30 add 11 7 add 8 26 swap 19 6 add 21 13 swap 28 16 swap 11 18 add 26 14 swap 14 8 swap 11 24 ...
output:
550095038 92418381 507176887 906163279 313105934 570651164 285313314 517015518 438637289 250415289 6...
result:
ok 30 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 1568kb
input:
30 30 30 swap 5 5 swap 21 3 add 17 1 swap 11 23 add 9 29 add 23 1 add 23 3 swap 23 21 add 3 21 swap ...
output:
287688536 772489543 549962788 868362009 689988914 853729914 20144151 714205769 402286427 810161567 4...
result:
ok 30 lines
Test #3:
score: 10
Accepted
time: 166ms
memory: 4144kb
input:
100 100 100 swap 6 80 swap 88 53 swap 55 59 swap 45 81 swap 4 56 swap 69 85 swap 71 93 swap 97 58 sw...
output:
749336717 24709802 840318246 634954155 259909581 258599455 649551653 296218244 72544480 896050158 31...
result:
ok 100 lines
Test #4:
score: 10
Accepted
time: 163ms
memory: 4112kb
input:
100 100 100 swap 50 26 swap 42 30 swap 43 14 swap 88 24 swap 33 75 swap 84 39 swap 28 46 swap 11 33 ...
output:
772590331 74462880 377435932 687433410 392067538 166828233 215084806 318363631 161238800 327773751 3...
result:
ok 100 lines
Test #5:
score: 10
Accepted
time: 1507ms
memory: 4148kb
input:
100 1000000 1 add 61 62 swap 33 93 swap 86 6 swap 72 16 add 11 94 swap 39 47 swap 41 49 swap 19 6 ad...
output:
346253799 771126444 971288221 851217895 505808154 221609458 688027614 70353229 288594725 941298229 4...
result:
ok single line: '346253799 771126444 971288221 ...4 52682545 701646733 382173771 '
Test #6:
score: 10
Accepted
time: 1088ms
memory: 4144kb
input:
100 1000000 1 add 5 7 swap 87 70 add 74 61 swap 12 64 add 44 9 add 54 6 swap 86 97 swap 28 85 swap 5...
output:
450803790 667372094 419301609 389943582 752771140 804124829 585325182 72383423 966194784 233403679 3...
result:
ok single line: '450803790 667372094 419301609 ... 713392549 328208981 322568321 '
Test #7:
score: 10
Accepted
time: 1485ms
memory: 4144kb
input:
100 1000000 1 add 46 61 add 45 43 swap 62 17 swap 52 8 swap 74 33 swap 76 56 add 35 38 swap 37 69 ad...
output:
125149011 756465812 161024297 688771858 867501504 650402763 595197506 873222233 587955871 81643619 3...
result:
ok single line: '125149011 756465812 161024297 ...2 91971529 757776826 634397245 '
Test #8:
score: 10
Accepted
time: 988ms
memory: 4148kb
input:
100 1000000 100 swap 91 58 swap 100 84 swap 15 59 swap 50 98 add 5 45 add 24 15 swap 37 2 add 2 55 s...
output:
977736656 530446270 797215529 884989997 700839061 290600516 76651241 425687312 559634624 35286388 41...
result:
ok 100 lines
Test #9:
score: 10
Accepted
time: 950ms
memory: 4148kb
input:
100 1000000 100 swap 43 7 add 49 61 add 3 18 swap 90 50 add 34 72 swap 47 73 swap 86 51 swap 12 38 a...
output:
883102546 725800572 971218181 922364443 269815718 329364304 159331295 428667708 3431691 503434529 15...
result:
ok 100 lines
Test #10:
score: 10
Accepted
time: 1314ms
memory: 4148kb
input:
100 1000000 100 swap 84 65 add 3 34 swap 91 74 swap 33 94 swap 80 83 swap 69 27 swap 27 99 swap 21 1...
output:
147983174 81716446 161911525 667483078 170580251 709287671 728191563 271802648 733606284 754329389 8...
result:
ok 100 lines
Extra Test:
score: 0
Extra Test Passed
