kojingharangの日記

Codeforces 105 Div2 E. Lucky Subsequence

12:25 |

できなかった問題を editorial や他の人のコードを見ながら書いてみるシリーズ。

N, K, 長さ N の数列が与えられるので、数列から K 個を選ぶ方法の数を MOD 1000000007 で出力する。

ただし、各桁が 4 or 7 だけでできている lucky number に関しては同じ数字を１回までしか使ってはいけない。という問題。

非 lucky number の数字を２回以上使う場合、同じ数字でも取ってくる元の位置が違えば異なるとみなす。

lucky number を i 個使った場合、K-i 個の非 lucky number を選ぶ組み合わせは「非lucky numberの個数 C K-i」になる

lucky number の選び方は...

10**9 以下の lucky number は 1022 個しかないので、次の DP が考えられる。

dp[pos][cnt]

pos: 何番目までの lucky number を使ったか (0-)

cnt: lucky number をいくつ使ったか

dp[i][0] = 1
dp[i][j] =   dp[i-1][j]              (i番目を使わない場合)
          + dp[i-1][j-1] * count[i] (i番目を使う場合、その数の出現個数だけ選択肢がある)

nl : lucky number の(重複を除いた)個数

rest : 非lucky numberの個数

comb : 二項係数

で最終的な答えは Σi=[0, nl] comb(rest, K-i) * dp[nl][i] で計算できる。

で、いくつか知見が得られた。（間違ってたら指摘お願いします..）

ツイートする

M を法とする a の逆元

12:25 |

gcd(M, a)==1 の場合、extgcd(a, M, x, y) として x が a の逆元。

// ax+by=gcd(a,b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
   ll g = a; x = 1; y = 0;
   if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
   return g;
}

特に M が素数の場合、フェルマーの小定理より a**(M-2) mod M が a の逆元。

a**(M-1) ≡ 1 mod M → a * a**(M-2) ≡ 1 mod M なので。

参考

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Cong.html

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html

http://www.prefield.com/algorithm/math/gcd.html

ツイートする

nC0, nC1, ..., nCr mod M を求める

12:25 |

nCr mod M = ( Π(i in [1, r]) n-i+1 / i ) mod M

= Π(i in [1, r]) n-i+1 * inv(i) mod M

ということで、ループの i 回目の時点で nCi が求まる。その都度結果を保存していけば O(r) で nC0 から nCr まで計算できる。

もしくは、1!, 2!, ..., n! まで逆元も含めて求めておいて n!/(r! * (n-r)!) = n! * inv(r!) * inv((n-r)!) としてもいい。

ツイートする

コード (practice で accepted)

12:25 |

（LuXueQi さん、xhl_kogitsune さんのコードも参考にしました）

#define MOD 1000000007LL
#define MAXN 100003
int dp[1024][1024];
int b[MAXN];

int lucky(ll x) {
   for(;x>0;x/=10) if(x%10!=4 && x%10!=7) return 0;
   return 1;
}

ll modpow(ll v, int p) {
   if(p==1) return v;
   ll vv = modpow(v, p/2);
   vv = (vv * vv) % MOD;
   if(p&1) vv = (vv * v) % MOD;
   return vv;
}

ll comb(int n, int k) {
   ll c=1;
   for(int i=1;i<=k;i++) {
        c = (c * (n-i+1)) % MOD;
        c = (c * modpow(i, MOD-2)) % MOD;
   }
   return c;
}

int main() {
   int N,K;
   cin>>N>>K;
   memset(dp, 0, sizeof(dp));

   map<ll, int> hi;
   VI lu;
   int rest=0;
   REP(i, N) {
        int v;
        scanf("%d",&v);
        if(lucky(v)) {
             if(hi[v]==0) lu.PB(v);
             hi[v]++;
        }
        else rest++;
   }
   int nl=hi.size();

   dp[0][0] = 1;
   for(int y=1;y<=nl;y++) {
        dp[y][0] = 1;
        for(int x=1;x<=nl;x++) {
             dp[y][x] = ( dp[y-1][x] + ((ll)dp[y-1][x-1] * hi[lu[y-1]])%MOD ) % MOD;
        }
   }

   b[0]=1;
   for(int i=1;i<=rest;++i){
        b[i]=1LL*b[i-1]*(rest-i+1)%MOD*modpow(i, MOD-2)%MOD;
   }

   ll ans = 0;
   REP(i, nl+1) {
        int lrest = K-i;
        if(lrest < 0 || rest < lrest ) continue;
        ans += (ll)b[lrest] * dp[nl][i];
        ans = ans % MOD;
   }
   cout<<ans<<endl;

   return 0;
}

ツイートする