NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #204859 | #3630. 数列操作 | smallstone | 100 | 4090ms | 5192kb | C++11 | 2.3kb | 2024-06-10 11:25:49 | 2024-06-10 12:06:01 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
#define mod 1000000007ll
#define N 29
ll n = 100, m, q;
struct mat
{
ll a[111][111];
mat(ll op = 0)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = ((i == j) && op);
}
};
struct mat1
{
ll b[111];
mat1(){
for (int i = 1; i <= n; i++)
b[i] = 0;
}
}r, nr;
mat omg(1), op[40];
mat operator*(mat &a, mat &b)
{
mat ans;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
return ans;
}
mat1 operator*(mat1 &y, mat &b)
{
mat1 ans;
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
ans.b[j] = (ans.b[j] + y.b[k] * b.a[k][j] % mod) % mod;
return ans;
}
void print(mat t)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
printf("%lld ", t.a[i][j]);
puts("");
}
}
void print(mat1 t)
{
for (int j = 1; j <= n; j++)
printf("%lld ", t.b[j]);
puts("");
}
mat1 qpow(mat1 res, ll y)
{
for(ll i = 0 ; i <= N ; i++)
if(y & (1ll << i)){
//puts("");print(res);
//print(op[i]);
res = res * op[i];
//print(res);puts("");
//cout << i << " ";
}
return res;
}
mat qpow(mat res, ll y)
{
mat ans(1);
while (y)
{
if (y & 1)
ans = ans * res;
res = res * res;
y >>= 1;
}
return ans;
}
char s[11];
ll x, y, a[111], k;
int main(){
scanf("%lld%lld%lld", &n, &m, &q);
for(int i = 1 ; i <= m ; i++){
scanf("%s%lld%lld", s, &x, &y);
if(s[0] == 's'){
for(int j = 1 ; j <= n ; j++)
swap(omg.a[j][x], omg.a[j][y]);
//swap(omg.a[x][x], omg.a[y][x]);
//swap(omg.a[y][x], omg.a[y][y]);
//swap(omg.a[x][y], omg.a[y][y]);
}
else{
for(int j = 1 ; j <= n ; j++)
{
omg.a[j][x] += omg.a[j][y];
omg.a[j][x] %= mod;
}
}
//print(omg);
}
//print(omg);
op[0] = omg;
for(ll i = 1 ; i <= N ; i++){
op[i] = op[i - 1] * op[i - 1];
//print(op[i]);
}
for(int i = 1 ; i <= q ; i++){
//memset(nr.b, 0, sizeof nr.b);
for(int j = 1 ; j <= n ; j++)
scanf("%lld", &r.b[j]);
scanf("%lld", &k);
nr = qpow(r, k);
//print(nr);
for(int j = 1 ; j <= n ; j++){
printf("%lld%c", nr.b[j], " \n"[j == n]);
nr.b[j] = 0;
}
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 5ms
memory: 5128kb
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: 8ms
memory: 5132kb
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: 275ms
memory: 5184kb
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: 165ms
memory: 5192kb
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: 529ms
memory: 5192kb
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 ...24 52682545 701646733 382173771'
Test #6:
score: 10
Accepted
time: 515ms
memory: 5192kb
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 ...7 713392549 328208981 322568321'
Test #7:
score: 10
Accepted
time: 519ms
memory: 5188kb
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 ...42 91971529 757776826 634397245'
Test #8:
score: 10
Accepted
time: 604ms
memory: 5192kb
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: 578ms
memory: 5188kb
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: 892ms
memory: 5188kb
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
