千万注意，是%=，而不是%

(sum+=value[i][len[i]]*g[j])%=mod; 与

(sum+=value[i][len[i]]*g[j])%mod;　　//wrong

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 using namespace std; 9 #define ll long long10 11 const double eps=1e-8;12 const ll inf=1e9;13 const ll mod=998244353;14 const int maxn=1e5+10;15 16 ll len[maxn],a[maxn],value[maxn][21],ext[maxn][21],ch[21],g[21];17 18 ll cal(ll d)19 {20 ll tot=0;21 while (d)22 {23 tot++;24 d/=10;25 }26 return tot;27 }28 29 int main()30 {31 ll i,j,k,n,d,sum=0,add;32 ch[0]=1;33 for (i=1;i<=20;i++)34 ch[i]=ch[i-1]*10%mod;///10^i35 36 scanf("%lld",&n);37 for (i=1;i<=n;i++)38 {39 scanf("%lld",&a[i]);40 d=a[i];41 len[i]=cal(d);42 g[len[i]]++;43 44 j=1;45 add=0;46 while (d)47 {48 (add+=d%10*ch[j*2-2])%=mod;49 value[i][j]=add*11%mod;50 d/=10;51 ext[i][j]=d*ch[j*2]*2%mod;52 j++;53 }54 // printf("z");55 }56 57 for (i=1;i<=n;i++)58 {59 k=len[i];60 for (j=1;j<=10;j++)61 if (k<=j)62 (sum+=value[i][len[i]]*g[j])%=mod;63 else64 {65 (sum+=(value[i][j]+ext[i][j])*g[j])%=mod;66 }67 }68 69 printf("%lld",sum);///why70 return 0;71 }72 /*73 574 1000000000 1000000000 1000000000 1000000000 100000000075 76 in codeblocks, answer is wrong?77 ³¢ÊÔÌá½»£¿78 */
           
          
         
        
       
      
     

 

 

套路单调队列题

从上到下记录a*1，然后从左往右记录a*b(若干个a*1)

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 using namespace std; 9 #define ll long long10 11 const double eps=1e-8;12 const ll inf=1e9;13 const ll mod=1e9+7;14 const int maxn=3e3+10;15 16 ll h[maxn][maxn],pos[maxn];17 ll col[maxn][maxn];18 19 int main()20 {21 ll sum=0;22 ll n,m,a,b,i,j;23 ll g0,x,y,z;24 ll head,tail;25 scanf("%lld%lld%lld%lld",&n,&m,&a,&b);26 scanf("%lld%lld%lld%lld",&g0,&x,&y,&z);27 for (i=1;i<=n;i++)28 for (j=1;j<=m;j++)29 {30 h[i][j]=g0;31 g0=(1ll*g0*x+y)%z;32 }33 34 35 for (j=1;j<=m;j++)36 {37 head=1,tail=0;38 for (i=1;i<=n;i++)39 {40 while (head<=tail && pos[head]<=i-a)41 head++;42 while (head<=tail && h[pos[tail]][j]>=h[i][j])43 tail--;44 tail++;45 pos[tail]=i;46 col[i][j]=h[pos[head]][j];47 }48 }49 50 for (i=a;i<=n;i++)51 {52 head=1,tail=0;53 for (j=1;j<=m;j++)54 {55 while (head<=tail && pos[head]<=j-b)56 head++;57 while (head<=tail && col[i][pos[tail]]>=col[i][j])58 tail--;59 tail++;60 pos[tail]=j;61 if (j>=b)62 sum+=col[i][pos[head]];63 }64 }65 printf("%lld",sum);66 return 0;67 }68 /*69 3 4 2 170 1000000000 1000000000 1 23414271 */