CF 145C: Lucky Subsequence

很简单的一道欧拉函数相关的题。。

但是我实在是对数论不熟，各种小错导致调了很久 T^T

题目链接：http://codeforces.com/contest/345/problem/C

通过这道题学习了欧拉函数的相关知识

逆元可以利用扩展欧几里德或欧拉函数求得（p为质数）：

1).扩展欧几里德：b*x+p*y=1 有解，x就是所求

2).欧拉函数：b^(p-1)=1(mod p),故b*b^(p-2)=1(mod p),所以x=b^(p-2) 以上黄色部分引用自waitfor_的博客，非常感谢。

1、费马定理：a的p-1次方mod p余1。（其中p是素数，a是不能被p整除的正整数)

2、欧拉定理

2.1 欧拉函数

定义：欧拉函数phi(m)：当m>1时，phi(m)表示比m小且与m互质的正整数个数

性质：（1）当m为素数时，phi(m)=m-1

         （2）当m=pq，且p和q是互异的素数，                  则有：phi(m)=phi(p)*phi(p)=(p-1)(q-1) （这很好用）

         （3）m＝p^e，且p为素数，e为正整数，则

                 phi(m)=p^e-p^(e-1)=(p^(e-1))*(p-1) 

定理：若m=p1^e1*p2^e2....pt^et则：

         phi(m)=m(1-1/p1)(1-1/p2)....(1-1/pt) （pi是素数）

2.2 欧拉定理

      a^phi(n)=1 mod n

      注：[1]n=p时候，有a^(p-1)=1 mod p，为费马定理

            [2]a^(phi(n)+1)=a mod n

            [3]若n=pq，p与q为相异素数，取大于0的m,n互质数，有

                 m^(phi(n)+1)=m mod n; m^((p-1)(q-1)+1)=m mod n 以上蓝色部分引自《一个数论里的概念 本原元》，同样感谢 > <

代码如下：

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MAXN=1100;
const int MAXM=110000;
int cot[10][1<<10];
long long d[MAXN][MAXN];
long long m[MAXM];
const long long mod=1000000007;

int f(int x) {
    int tot=0,ret=0;
    while(x) {
        tot++;
        int y=x%10;
        x/=10;
        if(y==4) {
            ret=(ret<<1)^1;
        } else if(y==7) {
            ret<<=1;
        } else return 0;
    }
    if(tot) {
        cot[tot][ret]++;
        if(cot[tot][ret]>1) {
            return 1;
        }
    }
    return 0;
}

long long pown(int x,int k) {
    long long ans=1LL;
    long long ret=x;
    while(k) {
        if(k&1) {
            ans=(ans*ret)%mod;
        }
        ret=(ret*ret)%mod;
        k>>=1;
    }
    return ans;
}


long long C(int n, int k) {
    if(n<k) {
        return 0LL;
    }
    long long ans=m[n];
    ans=(ans*pown(m[n-k],mod-2))%mod;
    ans=(ans*pown(m[k],mod-2))%mod;
    return ans;
}

int main() {
    int n,k;
    m[0]=1;
    for(int i=1; i<MAXM; i++) {
        m[i]=(m[i-1]*i)%mod;
    }
    while(scanf("%d%d",&n,&k)==2) {
        memset(cot,0,sizeof(cot));
        int ret=0;
        for(int i=0; i<n; i++) {
            int x;
            scanf("%d",&x);
            ret+=f(x);
        }
        n-=ret;
        if(n<k) {
            puts("0");
            continue;
        }
        long long ans=0LL;
        int tot=0;
        memset(d,0,sizeof(d));
        d[0][0]=1LL;
        for(int i=1; i<10; i++) {
            for(int j=0; j<(1<<i); j++) {
                if(cot[i][j]) {
                    tot++;
                    for(int num=tot; num; num--) {
                        d[tot][num]=(d[tot-1][num]+d[tot-1][num-1]*cot[i][j])%mod;
                    }
                    d[tot][0]=d[tot-1][0];
                }
            }
        }
        for(int j=0; (j<=k)&&(j<=tot); j++) {
            ans+=(d[tot][j]*C(n-tot,k-j))%mod;
            ans%=mod;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}