QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390525 | #3735. Reverse | 秦始皇派蒙恬还原神舟十二 (Jiancong Wen, Chu Jin, Zekai Zhang) | AC ✓ | 4ms | 6964kb | C++20 | 2.0kb | 2024-04-15 16:30:10 | 2024-04-15 16:30:10 |
Judging History
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"