kmjp's blog

競技プログラミング参加記です

TopCoder SRM 748 Div1 Easy, Div2 Hard EraseToGCD

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)を答えればよい。
  • 包除原理で解く。
    • f(k) := GCDがkの倍数になる組み合わせ、とすると、f(k)はS中のkの倍数の要素数mに対しf(k)=2^m-1となる。
    • g(k) := GCDがkの倍数になる組み合わせ、とするとg(k) = f(k) - g(2k) - g(3k) - ...なのでg,fを大きい順に求めていけばよい。

本番は後者で解いたが、前者の方が楽だね。以下のコードは前者。

 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];
		
		
	}
}

まとめ

なぜ遠回りしてしまったのか。