QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390525#3735. Reverse秦始皇派蒙恬还原神舟十二 (Jiancong Wen, Chu Jin, Zekai Zhang)AC ✓4ms6964kbC++202.0kb2024-04-15 16:30:102024-04-15 16:30:10

Judging History

This is the latest submission verdict.

  • [2024-04-15 16:30:10]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 6964kb
  • [2024-04-15 16:30:10]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define pii pair<int,int>

const int N = 1e6 + 20;
const int mod = 1e9 + 7;
// char a[N];
string a;
int s[N], ss[N];
int b[N];
int c[N];
int n;
void solve()
{
   
   // cin >> n >> a;
   int ans = (n * (n + 1))/2;
   ans %= mod;
   s[0] = 0;
   for(int i = 0; i < n; i++)
   {
      b[i] = a[i] - '0';
      s[i] = b[i];
      if(i != 0)
      {
         s[i] += s[i - 1];
      }
      s[i] %= mod;
      // cout << s[i] << " ";
   }
   int ret = n - 1;
   for(int i = 0, j = n - 1; i < n/2; i ++, j --)
   {
      ans = ((ans - ret + mod) % mod + mod) % mod;
      // ans -= ret;
      ret -= 2;
      // cout << " **"<< ans << " ";
      if(i == 0)
      {
         ss[i] = s[n - 1];
      }
      else
      {
         ss[i] = (ss[i - 1] + (s[j] - s[i - 1]) % mod) % mod;
      }
      c[i] =((ss[i] - (i + 1) * b[i] + ans * b[i] + mod) % mod + mod) % mod;
      ss[i] %= mod;
      c[i] %= mod;
   } 
   ans = (n * (n + 1))/2, ret = n - 1;
   ans %= mod;
   for(int i = n - 1, j = 0; j < n/2; i--, j ++)
   {
       ans = ((ans - ret + mod) % mod + mod) % mod;
      ret -= 2;
      // cout << " **"<< ans << " ";
      if(i == n - 1)
      {
         ss[i] = s[n - 1];
      }
      else
      {

         ss[i] = ((ss[i + 1] + (s[i] - s[j - 1])) % mod) % mod;
      }
      c[i] = ((ss[i] - (j + 1) *b[i] + ans * b[i] + mod) % mod + mod) % mod;
   }
   if(n % 2)
   {
      c[n/2] = ((c[n/2 - 1] + ans * b[n/2] - b[n/2] * (n/2) - ans * b[n/2 - 1] + b[n/2 - 1] * (n/2)+ mod) % mod + mod)%mod;
   }
   int ret1 = 1;
   ans = 0;
   for(int i = 0, j = n - 1; i < n; i ++, j--)
   {
      // cout << c[j] << " ";
         ans = (ans + (ret1 % mod * c[j] ) % mod)%mod;
         ret1 = (ret1 % mod * 10 % mod) % mod;
         // cout << ret1 << " ";
   }
   cout << ans << "\n";
}

signed main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
    int T = 1;
   //  cin >> T;
	while( cin >> n >> a)
	{
		solve();
	}
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

100
7723432185251080044559434422189260818487742686093976306463465325903335412616796193603237469341367960

output:

960961876

result:

ok 1 number(s): "960961876"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

100
9864307955690302185283215997090778379782417870018929428342752298148632025050839300716200413664138081

output:

965756099

result:

ok 1 number(s): "965756099"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

100
9907470924162703337926098353000318032199890056730660739401120360172020820406984286916173477097799014

output:

772430990

result:

ok 1 number(s): "772430990"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

100
1158362912502025588688079828111827583694255240773621939390497211016227414751038483019354520310568126

output:

360019861

result:

ok 1 number(s): "360019861"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

100
3091137872943327727321850295111535244999630234597662051370784284240534207197063690101327584534309149

output:

326618001

result:

ok 1 number(s): "326618001"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

100
5252000841413748878185513779242045807306315517410403252239061167184932802543916596202298758877960271

output:

907486271

result:

ok 1 number(s): "907486271"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

100
5395175819855040229818304144252563568601769701222344362318330218318119695988072703404261812290731284

output:

123878000

result:

ok 1 number(s): "123878000"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

100
7436068680514442468550386600363193022016144917145384685177627180253428490534105781587244864524592324

output:

318640301

result:

ok 1 number(s): "318640301"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

100
5059415932743570151682705131153127209621755255586507103119780921479716978264347061240014867920674148

output:

582644369

result:

ok 1 number(s): "582644369"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

100
7991287721202992302324486707063837760026119439421348104299057074314195561619202269332097929133215169

output:

579416634

result:

ok 1 number(s): "579416634"

Test #12:

score: 0
Accepted
time: 4ms
memory: 6892kb

input:

100000
41953145703584328585316398935500515081968159697809084328375989877609998924225365214411384299579347201964500885136587415210752217571847682172500554003298975209734142396850661748826619537443977601434648717840681222451686037953783740970848842858243134147808873060522855493009866017755703043412160...

output:

111992448

result:

ok 1 number(s): "111992448"

Test #13:

score: 0
Accepted
time: 0ms
memory: 6904kb

input:

100000
63662995487207319992846104584515891694013909455039486528168657396951956978885817386210094733907056522747706368404597017721650465793734293901893939669408930350503264290170027557379223283473482186443367276479538248565087727722158284095584056355780569992209044582501032808235152842074961085491484...

output:

172311286

result:

ok 1 number(s): "172311286"

Test #14:

score: 0
Accepted
time: 0ms
memory: 6964kb

input:

100000
84091616062691531489284917246610998228069541394257897657931528028395742802126256367240724576145668755203232821973598519944645784806731525631095394205698994292282564904381685466630837658491869863332884737095585296778688737402633627090427170882415913529782417196680429403450741587493008748580707...

output:

725313831

result:

ok 1 number(s): "725313831"

Test #15:

score: 0
Accepted
time: 4ms
memory: 6908kb

input:

100000
86400364776214553996602543995727073833113293232486400658535397737638810856775708418360555010571377888786537294342497381464543932009637136668386748840908759144052766618301053364992440014541574540143513916623414323870090528293031261105491183517030337363286608608669606739575228412910175779578020...

output:

228617638

result:

ok 1 number(s): "228617638"

Test #16:

score: 0
Accepted
time: 0ms
memory: 6912kb

input:

100000
05831094450717766303230456557032280446187045072726812887328068267070897700236238489179265643609789209542763777630486883777331280101424568498569925498198705284811887612513611173255234669561969028122133486140461571883691438072416726129336117034775782998587771119658981344701714057169433433577343...

output:

295359618

result:

ok 1 number(s): "295359618"

Test #17:

score: 0
Accepted
time: 2ms
memory: 6840kb

input:

100000
26249922145323788890677262206139365970332676919956243887019936098313965635696599261199995287047498312027267231109488486297428217322221171227760470034301568157600989326832079062426847115791446705011850845778191607907092220631681360224079241542400116845160142823636168649946303792588490276546657...

output:

528116908

result:

ok 1 number(s): "528116908"

Test #18:

score: 0
Accepted
time: 4ms
memory: 6908kb

input:

100000
28858672841726700305907095066243662583488428879174655998802607798737941689147021312229626700273000635580483712479397958738326567525337793955051834670691524099469181050862655983768551591811952482820379104394148655099693030322087804239023245079147560480464335335615545254860889628007757137634970...

output:

757627467

result:

ok 1 number(s): "757627467"

Test #19:

score: 0
Accepted
time: 0ms
memory: 6888kb

input:

100000
49389303426220912713545801717240747197452270618323066117605576220089719503506571393220326542401619865366917175946398550940111715627114124784254289117801589149239413754083013792021156946869347979711898565923095681212004929101462469334988279704772995217957597847694740651095376263234825981633293...

output:

92007413

result:

ok 1 number(s): "92007413"

Test #20:

score: 0
Accepted
time: 0ms
memory: 6924kb

input:

100000
25401064258609209426749886035260009083496073092736281306826024639362693480908894992666958456571447083588814774069662164606740203486000767897040499582695705915796846901745204121919446286587152214641694785955265400552683133207966092008372021862248894228853133964546046633985669891370048969318760...

output:

270394093

result:

ok 1 number(s): "270394093"

Test #21:

score: 0
Accepted
time: 4ms
memory: 6920kb

input:

100000
46832794943123220943077611784475484697462825159954693305619995351615581336359326963488759099707839304041311157537673666129847451608807398627233854048905740765566967625964862932280050632607537791530313144583122656474095123066331536123335155397963228075336324678525243148130166626599216820307084...

output:

842362971

result:

ok 1 number(s): "842362971"