NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213292 | #3850. 因子数列 | one_zero_four_zero | 0 | 1143ms | 3280kb | C++11 | 2.2kb | 2024-11-10 12:31:55 | 2024-11-10 13:07:37 |
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mod 998244353LL
using namespace std;
struct Matrix{
int r, c;
long long data[505][505];
Matrix operator * (const Matrix &a) const{
Matrix res;
res.r = r, res.c = a.c;
for (int i = 1; i <= res.r; i ++){
for (int j = 1; j <= res.c; j ++){
res.data[i][j] = 0;
}
}
for (int i = 1; i <= res.r; i ++){
for (int j = 1; j <= res.c; j ++){
for (int k = 1; k <= c; k ++){
res.data[i][j] += data[i][k] * a.data[k][j];
res.data[i][j] %= mod;
}
}
}
return res;
}
};
int Q;
long long M, N;
// long long dp[1003][1003];
vector<int> fac;
Matrix qpow(Matrix a, long long b){
Matrix res;
res.r = res.c = a.r;
/*
for (int i = 1; i <= res.r; i ++){
for (int j = 1; j <= res.c; j ++){
if (i == j) res.data[i][j] = 1;
else res.data[i][j] = 0;
}
}
while (b){
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
*/
return res;
}
void __init(){
fac.push_back(-1);
for (int i = 1; i <= M / i; i ++){
if (M % i) continue;
fac.push_back(i);
if (M / i != i) fac.push_back(M / i);
}
sort(fac.begin(), fac.end());
}
int main(){
#ifndef ONLINE_JUDGE
freopen("../data.in", "r", stdin);
freopen("../data.out", "w", stdout);
#endif
scanf("%lld %d", &M, &Q);
__init();
/*
for (int i = 1; i < fac.size(); i ++) dp[1][i] = 1;
for (int i = 1; i <= 1000; i ++){
for (int j = 1; j < fac.size(); j ++){
printf("%-9d ", dp[i][j]);
for (int k = 1; k < fac.size(); k ++){
if (__gcd(fac[j], fac[k]) == 1) continue;
dp[i + 1][k] += dp[i][j];
dp[i + 1][k] %= mod;
}
}
cout << "\n";
}
*/
Matrix cur;
cur.r = cur.c = fac.size() - 1;
for (int i = 1; i < fac.size(); i ++){
for (int j = 1; j < fac.size(); j ++){
if (__gcd(fac[i], fac[j]) == 1) cur.data[i][j] = 0;
else cur.data[i][j] = 1;
}
}
while (Q --){
scanf("%lld", &N);
Matrix ans;
ans.r = 1, ans.c = fac.size() - 1;
for (int i = 1; i < fac.size(); i ++) ans.data[1][i] = 1;
ans = ans * qpow(cur, N - 1);
long long cnt = 0;
for (int i = 1; i < fac.size(); i ++){
cnt = (cnt + ans.data[1][i]) % mod;
}
printf("%lld\n", cnt % mod);
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 23ms
memory: 3268kb
input:
210 200 113 296 253 65 203 145 64 55 50 77 43 251 260 55 156 265 297 230 119 294 120 42 208 243 269 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '935976218', found: '0'
Test #2:
score: 0
Wrong Answer
time: 2ms
memory: 3264kb
input:
252 1 314055503869010724
output:
0
result:
wrong answer 1st numbers differ - expected: '909628637', found: '0'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3256kb
input:
282 1 264777687269675469
output:
0
result:
wrong answer 1st numbers differ - expected: '701846098', found: '0'
Test #4:
score: 0
Wrong Answer
time: 23ms
memory: 3264kb
input:
290 200 802726718582470993 513758619815309942 189274088962622536 860983948867274839 3577502703482725...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '432215483', found: '0'
Test #5:
score: 0
Wrong Answer
time: 289ms
memory: 3280kb
input:
58198140 200 959 862 510 520 426 547 672 141 111 147 520 962 909 302 854 306 934 524 733 649 886 695...
output:
0 150816582 150816582 150816582 150816582 150816582 150816582 150816582 150816582 150816582 15081658...
result:
wrong answer 1st numbers differ - expected: '384775834', found: '0'
Test #6:
score: 0
Wrong Answer
time: 5ms
memory: 3272kb
input:
62180118 1 926181104898054637
output:
0
result:
wrong answer 1st numbers differ - expected: '937298991', found: '0'
Test #7:
score: 0
Wrong Answer
time: 8ms
memory: 3276kb
input:
95611230 1 182274277242753806
output:
0
result:
wrong answer 1st numbers differ - expected: '125901080', found: '0'
Test #8:
score: 0
Wrong Answer
time: 354ms
memory: 3280kb
input:
95233320 200 345690473651689621 377192517307333764 491266035915286354 277537088705458756 69755658847...
output:
0 427444653 427444653 427444653 427444653 427444653 427444653 427444653 427444653 427444653 42744465...
result:
wrong answer 1st numbers differ - expected: '279092297', found: '0'
Test #9:
score: 0
Wrong Answer
time: 439ms
memory: 3280kb
input:
85765680 200 842604215470675913 693968348917184945 194347127230511886 923041766224662131 52394950648...
output:
0 66439952 66439952 66439952 66439952 66439952 66439952 66439952 66439952 66439952 66439952 66439952...
result:
wrong answer 1st numbers differ - expected: '263864344', found: '0'
Test #10:
score: 0
Runtime Error
input:
802241960520 1 337589677349356513
output:
result:
Test #11:
score: 0
Runtime Error
input:
644348954340 1 130986907629009228
output:
result:
Test #12:
score: 0
Runtime Error
input:
705537072240 1 267882780122683404
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
776363187600 200 106688853771652749 752427214283496810 586926336522723525 681973907945298011 6448233...
output:
result:
Test #14:
score: 0
Runtime Error
input:
694247850450 200 465336166247569990 734514969437137822 774584419214433387 636222504876595962 7302379...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
9127507905816300 1 934417805794906683
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
8265306123944870 1 140182875145542025
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
8217027977558400 1 176919885071352138
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
9390889117209600 1 210913601057588245
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
6775660251360000 200 984345398232352633 978615808106577653 215878340541519263 332384616027183722 730...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
2869438341369600 200 461375240042131253 485682298432589970 179932945870690884 157449555540945918 910...
