結果
問題 | No.1481 Rotation ABC |
ユーザー |
|
提出日時 | 2021-03-08 22:11:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 3,243 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 82,432 KB |
最終ジャッジ日時 | 2024-10-10 11:37:21 |
合計ジャッジ時間 | 4,272 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
class BIT():def __init__(self,n,mod=0):self.BIT=[0]*(n+1)self.num=nself.mod = moddef query(self,idx):res_sum = 0while idx > 0:res_sum += self.BIT[idx]if self.mod:res_sum %= self.modidx -= idx&(-idx)return res_sum#Ai += x O(logN)def update(self,idx,x):while idx <= self.num:self.BIT[idx] += xif self.mod:self.BIT[idx] %= modidx += idx&(-idx)returnclass SegmentTree:def __init__(self, init_val, segfunc, ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.numfor i in range(n):self.tree[self.num + i] = init_val[i]for i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x, op=False):k += self.numif not op:self.tree[k] = xelse:self.tree[k] = self.segfunc(self.tree[k],x)while k > 1:k >>= 1self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1])def query(self, l, r):res = self.ide_elel += self.numr += self.numright = []while l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:right.append(self.tree[r-1])l >>= 1r >>= 1for val in right[::-1]:res = self.segfunc(res,val)return resimport sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())def cmb(n, r, mod):#コンビネーションの高速計算if ( r<0 or r>n ):return 0r = min(r, n-r)return g1[n] * g2[r] * g2[n-r] % modmod = 998244353 #出力の制限N = 2*10**5g1 = [1]*(N+1) # 元テーブルg2 = [1]*(N+1) #逆元テーブルinverse = [1]*(N+1) #逆元テーブル計算用テーブルfor i in range( 2, N + 1 ):g1[i]=( ( g1[i-1] * i ) % mod )inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )g2[i]=( (g2[i-1] * inverse[i]) % mod )inverse[0]=0N = int(input())S = input().rstrip()def solve(S):A = [i for i in range(N) if S[i]=="A"]B = [i for i in range(N) if S[i]=="B"]C = [i for i in range(N) if S[i]=="C"]a,b,c = len(A),len(B),len(C)if not a*b*c:return 1L,R = A[0],C[-1]for i in range(L,R):if S[i]=="B":res = g1[N]*g2[a]*g2[b]*g2[c]-Nreturn res % modL,R = B[0],A[-1]for i in range(L,R):if S[i]=="C":res = g1[N]*g2[a]*g2[b]*g2[c]-Nreturn res % modL,R = C[0],B[-1]for i in range(L,R):if S[i]=="A":res = g1[N]*g2[a]*g2[b]*g2[c]-Nreturn res % modreturn 1print(solve(S))