PTA | 程序设计类实验辅助教学平台
题目大意：有一个n位长的隐藏数x，从高位到低位依次标号为1到n，sum[i][j]表示从第i为开始每j位上的数的和，有q次询问，每次给出一个100以内除了5以外的质数p，问这个数%p等于多少
1<=t<=100；1<=n<=1e6；1<=i<=min(100,n)；1<=j<=i；1<=q<=10
思路：对于x的第i位，可以将其写成x[i]*，x%p就相当于x[1]*
%p+x[2]*
%p+...+x[n]*
%p。
如果%p=x，那么我们可以将每一项x[i]*
写成x[i]*(
-x)，这样的每一项%p都等于0，那么原式子不等于0的部分就是
%p*x[1]+
%p*x[2]+...+
%p*x[n]。
然后又发现%p是有循环节的，且循环节的长度是p-1，那么我们可以将上式拆成p-1个式子例如第一个式子是
%p*(x[1]+x[p]+x[2*p-1]+...)，第二个式子就是
%p*(x[2]+x[p+1]+x[2*p]+...)。
每个式子里后面括号中的数都是题目中给出的即sum[p-1][第i位]，所以可以在O(qtp)的时间复杂度内求出
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll sum[105][105];
void init()
{}
void solve()
{cin>>n;for(int i=1;i<=min(100,n);i++){for(int j=1;j<=i;j++){cin>>sum[i][j];}}int q;cin>>q;for(int i=1;i<=q;i++){ll mod;cin>>mod;vector<ll>m;ll x=1;for(int i=1;i<=mod-1;i++){//求出一个循环节m.push_back(x%mod);x=x*10%mod;}ll nn=n;ll ans=0;ll y=min(mod-1,nn);//如果p比n大，直接取sum的最后一行即可for(int i=1;i<=mod-1;i++){ll temp=nn%(mod-1);//第几位if(temp==0){temp=mod-2;}else{temp--;}ans=(ans+m[temp]*sum[y][i]%mod)%mod;nn--;}cout<<ans<<endl;}
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int t;cin>>t;while(t--){solve();}return 0;
}
