2連続レートを落としていたので、久々に復帰してよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15292
問題
N要素の整数列Sが与えられる。
Sの部分列のうち、GCDがGとなるものは何通りか。
解法
大きく2つ解法がある。
- 1つめはdp(n,k) := Sのprefix n個の部分列のうち、GCDがkとなるものの数。ただし部分列が0要素のときGCDは0とする
- (n+1)番目を部分列に加える場合と加えない場合を考え、最後にdp(N,G)を答えればよい。
- 包除原理で解く。
本番は後者で解いたが、前者の方が楽だね。以下のコードは前者。
ll dp[1010][1010]; ll mo=1000000007; class EraseToGCD { public: int countWays(vector <int> S, int goal) { int i,j,k; ZERO(dp); dp[0][0]=1; FOR(i,S.size()) { FOR(j,1001) if(dp[i][j]) { (dp[i+1][j]+=dp[i][j])%=mo; (dp[i+1][__gcd(S[i],j)]+=dp[i][j])%=mo; } } return dp[S.size()][goal]; } }
まとめ
なぜ遠回りしてしまったのか。