递归 8/10 MLE
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int T,n,m,k,a[N];
int f(int x,int k){
if(x==1)return 0;
return (f(x-1,k+1%m)+a[k % m])%x;
}
int main(){
cin >> T;
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d",&a[i]);
cout << f(n,0) << endl;
}
return 0;
}
递推 AC
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int T,n,m,a[N];
int f(int x,int k){
if(x==1)return 0;
return (f(x-1,k+1%m)+a[k % m])%x;
}
int main(){
cin >> T;
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d",&a[i]);
int ret=0;
for(int i = 2; i <= n; ++ i){
ret = (ret + a[(n - i) % m]) % i;
}
cout << ret << endl;
}
return 0;
}