結果

問題 No.1171 Runs in Subsequences
ユーザー Risu_BasquiatRisu_Basquiat
提出日時 2020-08-14 23:27:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 302 ms / 2,000 ms
コード長 3,823 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 109,084 KB
最終ジャッジ日時 2024-10-10 16:48:48
合計ジャッジ時間 5,119 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
84,284 KB
testcase_01 AC 124 ms
83,992 KB
testcase_02 AC 123 ms
84,356 KB
testcase_03 AC 123 ms
84,368 KB
testcase_04 AC 124 ms
84,456 KB
testcase_05 AC 123 ms
84,320 KB
testcase_06 AC 124 ms
84,292 KB
testcase_07 AC 123 ms
83,928 KB
testcase_08 AC 122 ms
84,048 KB
testcase_09 AC 122 ms
84,516 KB
testcase_10 AC 135 ms
88,840 KB
testcase_11 AC 139 ms
88,868 KB
testcase_12 AC 137 ms
88,816 KB
testcase_13 AC 140 ms
88,652 KB
testcase_14 AC 141 ms
88,536 KB
testcase_15 AC 293 ms
96,784 KB
testcase_16 AC 292 ms
97,060 KB
testcase_17 AC 302 ms
97,936 KB
testcase_18 AC 299 ms
98,276 KB
testcase_19 AC 300 ms
109,084 KB
testcase_20 AC 301 ms
107,856 KB
testcase_21 AC 300 ms
105,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    s=input()
    
    N=len(s)
    maxn=N
    fact=[1]*(maxn+1)#NはnCrの最大のn
    invs=[1]*(maxn+1);invs[0]=0
    ifact=[1]*(maxn+1)
    for i in range(2,maxn+1):
        fact[i]=(fact[i-1]*i)%mod
        invs[i]=invs[mod%i]*(-(mod//i))%mod
        ifact[i]=(ifact[i-1]*invs[i])%mod
    def perm(n,r): return fact[n]*ifact[n-r]%mod
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def multicomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    if N==1:
        print(1)
        return
    tot=0
    for i in range(1,N+1):
        tot=(tot+i*comb(N,i))%mod


    l=[[] for _ in range(26)]
    for i in range(N):
        si=s[i]
        sa=alp2num(si)
        l[sa].append(i)
    
    p2=[pow(2,i,mod) for i in range(N+1)]
    for i in range(26):
        li=l[i]
        if len(li)<2:
            continue
        lt=0
        r=0
        for lii in li:
            r+=p2[N-1-lii]
            r%=mod
        

        for j in range(len(li)-1):
            n=li[j]
            lt=p2[n]
            r-=p2[N-1-n]
            tot-=lt*r
            tot%=mod


    print(tot)





if __name__ == "__main__":
    main()
0