亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Password Attacker

系統(tǒng) 1941 0

Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:

Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password. However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.

To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on M keys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.

Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735. (And, in fact, there are 32 more possible passwords.)

However, these passwords are not possible:

1357 // There is no fingerprint on key '1'
3355 // There is fingerprint on key '7',
so '7' must occur at least once.
357 // Eve knows the password must be a 4-digit number.
With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).

Input

The first line of the input gives the number of test cases, T.
For the next T lines, each contains two space-separated numbers M and N, indicating a test case.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(109+7).

Limits

Small dataset

T = 15.
1 ≤ M ≤ N ≤ 7.
Large dataset

T = 100.
1 ≤ M ≤ N ≤ 100.
Sample

Input
4
1 1
3 4
5 5
15 15

Output?

Case #1: 1
Case #2: 36
Case #3: 120
Case #4: 674358851

google在線筆試題。這題一直沒做出來。有人說有公式,看到大牛們提交的代碼又覺得像是dp。后來學(xué)了生成函數(shù)之后,覺得應(yīng)該是一道指數(shù)型生成函數(shù)的題。

      
         1
      
       #include <iostream>


      
         2
      
       #include <cstdio>


      
         3
      
       #include <vector>


      
         4
      
      
         5
      
      
        using
      
      
        namespace
      
      
         std;


      
      
         6
      
      
        const
      
      
        double
      
       epi = 
      
        0.000001
      
      
        ;


      
      
         7
      
      
        int
      
       frac(
      
        int
      
      
         k) {


      
      
         8
      
      
        int
      
       ans = 
      
        1
      
      
        ;


      
      
         9
      
      
        for
      
       (
      
        int
      
       i = 
      
        2
      
      ; i <= k; ++
      
        i) {


      
      
        10
      
               ans *=
      
         i;


      
      
        11
      
      
            }


      
      
        12
      
      
        return
      
      
         ans;


      
      
        13
      
      
        }


      
      
        14
      
      
        15
      
      
        int
      
       enumPassword(
      
        int
      
       n, 
      
        int
      
      
         m) {


      
      
        16
      
           vector<vector<
      
        double
      
      > > 
      
        params
      
      (
      
        2
      
      , vector<
      
        double
      
      >(n + 
      
        1
      
      , 
      
        0
      
      
        ));


      
      
        17
      
      
        params
      
      [
      
        0
      
      ][
      
        0
      
      ] = 
      
        1
      
      
        ;


      
      
        18
      
      
        int
      
       cur = 
      
        0
      
      , next = 
      
        1
      
      
        ;


      
      
        19
      
      
        20
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < m; ++
      
        i) {


      
      
        21
      
      
        params
      
      [next].assign(n + 
      
        1
      
      , 
      
        0
      
      
        );


      
      
        22
      
      
        for
      
       (
      
        int
      
       j = 
      
        0
      
      ; j <= n; ++
      
        j) {


      
      
        23
      
      
        if
      
       (
      
        params
      
      [cur][j] < epi) 
      
        continue
      
      
        ;


      
      
        24
      
      
        for
      
       (
      
        int
      
       k = 
      
        1
      
      ; k + j <= n; ++
      
        k) {


      
      
        25
      
      
        params
      
      [next][k + j] = 
      
        params
      
      [next][k + j] + 
      
        params
      
      [cur][j] * 
      
        1
      
       /
      
         frac(k);


      
      
        26
      
      
                    }


      
      
        27
      
      
                }


      
      
        28
      
               cur = !cur; next = !
      
        next;


      
      
        29
      
      
            }


      
      
        30
      
      
        31
      
      
        return
      
      
        params
      
      [cur][n] *
      
         frac(n);


      
      
        32
      
      
        }


      
      
        33
      
      
        34
      
      
        int
      
       main(
      
        int
      
       argc, 
      
        char
      
      **
      
         argv) {


      
      
        35
      
      
        if
      
       (argc < 
      
        2
      
      ) 
      
        return
      
       -
      
        1
      
      
        ;


      
      
        36
      
           freopen(argv[
      
        1
      
      ], 
      
        "
      
      
        r
      
      
        "
      
      
        , stdin);


      
      
        37
      
      
        int
      
      
         test; 


      
      
        38
      
           scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        test);


      
      
        39
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < test; ++
      
        i) {


      
      
        40
      
      
        int
      
      
         m, n;


      
      
        41
      
               scanf(
      
        "
      
      
        %d%d
      
      
        "
      
      , &m, &
      
        n);


      
      
        42
      
               cout << 
      
        "
      
      
        Case #
      
      
        "
      
       << i + 
      
        1
      
       << 
      
        "
      
      
        : 
      
      
        "
      
       << enumPassword(n, m) <<
      
         endl;


      
      
        43
      
      
            }


      
      
        44
      
      
        45
      
      
        return
      
      
        0
      
      
        ;


      
      
        46
      
       }
    

但是數(shù)太大,要取模。除操作不能直接除模。

在網(wǎng)上搜到一個定理:

定理12.2:設(shè)$a_n$,$b_n$的指數(shù)生成函數(shù)分別為f(x)和g(x),則:

$f(x)*g(x) = \sum_{n=0}^{\infty}c_n\frac{x^n}{n!}, c_n = \sum_{k=0}^{n}C(n,k)a_kb_{n-k}$。

對應(yīng)到我們這里,Line 25里就變成params[cur][j]*1*C(j+k, k),params[cur][j]對應(yīng)的是$\frac{x^j}{j!}$的系數(shù),1對應(yīng)的是$\frac{x^k}{k!}$,所以乘以的就是C(j+k, k)了。

代碼如下:

      
         1
      
       #include <iostream>


      
         2
      
       #include <cstdio>


      
         3
      
       #include <vector>


      
         4
      
      
         5
      
      
        using
      
      
        namespace
      
      
         std;


      
      
         6
      
      
        enum
      
       {MOD = 
      
        1000000007
      
      
        };


      
      
         7
      
       typedef 
      
        long
      
      
        long
      
      
         llong;


      
      
         8
      
       llong combination[
      
        100
      
      ][
      
        100
      
      
        ];


      
      
         9
      
      
        void
      
      
         getCombination() {


      
      
        10
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i <= 
      
        100
      
      ; ++
      
        i) {


      
      
        11
      
      
        for
      
       (
      
        int
      
       j = 
      
        0
      
      ; j <= i; ++
      
        j) {


      
      
        12
      
      
        if
      
       (j == 
      
        0
      
      
        ) { 


      
      
        13
      
                   combination[i][j] = 
      
        1
      
      
        ;


      
      
        14
      
                   } 
      
        else
      
      
         {


      
      
        15
      
                       combination[i][j] = (combination[i - 
      
        1
      
      ][j] + combination[i - 
      
        1
      
      ][j - 
      
        1
      
      ]) %
      
         MOD;


      
      
        16
      
      
                    }


      
      
        17
      
      
                }


      
      
        18
      
      
            }


      
      
        19
      
      
        }


      
      
        20
      
      
        21
      
       llong enumPassword(
      
        int
      
       n, 
      
        int
      
      
         m) {


      
      
        22
      
           vector<vector<llong> > 
      
        params
      
      (
      
        2
      
      , vector<llong>(n + 
      
        1
      
      , 
      
        0
      
      
        ));


      
      
        23
      
      
        params
      
      [
      
        0
      
      ][
      
        0
      
      ] = 
      
        1
      
      
        ;


      
      
        24
      
      
        int
      
       cur = 
      
        0
      
      , next = 
      
        1
      
      
        ;


      
      
        25
      
      
        26
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < m; ++
      
        i) {


      
      
        27
      
      
        params
      
      [next].assign(n + 
      
        1
      
      , 
      
        0
      
      
        );


      
      
        28
      
      
        for
      
       (
      
        int
      
       j = 
      
        0
      
      ; j <= n; ++
      
        j) {


      
      
        29
      
      
        if
      
       (
      
        params
      
      [cur][j] == 
      
        0
      
      ) 
      
        continue
      
      
        ;


      
      
        30
      
      
        for
      
       (
      
        int
      
       k = 
      
        1
      
      ; k + j <= n; ++
      
        k) {


      
      
        31
      
      
        params
      
      [next][k + j] = (
      
        params
      
      [next][k + j] + 
      
        params
      
      [cur][j] * combination[j + k][k]) %
      
         MOD;


      
      
        32
      
      
                    }


      
      
        33
      
      
                }


      
      
        34
      
               cur = !cur; next = !
      
        next;


      
      
        35
      
      
            }


      
      
        36
      
      
        37
      
      
        return
      
      
        params
      
      
        [cur][n];


      
      
        38
      
      
        }


      
      
        39
      
      
        40
      
      
        int
      
       main(
      
        int
      
       argc, 
      
        char
      
      **
      
         argv) {


      
      
        41
      
      
        if
      
       (argc < 
      
        2
      
      ) 
      
        return
      
       -
      
        1
      
      
        ;


      
      
        42
      
           freopen(argv[
      
        1
      
      ], 
      
        "
      
      
        r
      
      
        "
      
      
        , stdin);


      
      
        43
      
      
        if
      
       (argc >= 
      
        3
      
      ) freopen(argv[
      
        2
      
      ], 
      
        "
      
      
        w
      
      
        "
      
      
        , stdout);


      
      
        44
      
      
            getCombination();


      
      
        45
      
      
        int
      
      
         test; 


      
      
        46
      
           scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        test);


      
      
        47
      
      
        for
      
       (
      
        int
      
       i = 
      
        0
      
      ; i < test; ++
      
        i) {


      
      
        48
      
      
        int
      
      
         m, n;


      
      
        49
      
               scanf(
      
        "
      
      
        %d%d
      
      
        "
      
      , &m, &
      
        n);


      
      
        50
      
      
        //
      
      
        cout << "Case #" << i + 1 << ": " << enumPassword(n, m) << endl;
      
      
        51
      
               printf(
      
        "
      
      
        Case #%d: %lld\n
      
      
        "
      
      , i + 
      
        1
      
      
        , enumPassword(n, m));


      
      
        52
      
      
            }


      
      
        53
      
      
        54
      
      
        return
      
      
        0
      
      
        ;


      
      
        55
      
       }
    

注意這里求組合數(shù)要用遞推公式來求,這樣可以在運算中取模,避免溢出。

$C(n, m) = C(n - 1, m) + C(n - 1, m - 1)$。

以后指數(shù)型生成函數(shù)的題都可以這么做。get!

Password Attacker


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日本不卡毛片一二三四 | 日韩专区中文字幕 | 青草视频在线 | 奇米影视亚洲春色77777 | 久久精品亚洲精品国产色婷 | 激情久久久久久久久久 | 卡通动漫精选国产欧美 | 国产亚洲精品成人一区看片 | 色一情一乱一乱91av | 亚洲精品三区 | 草视频在线观看 | 99热国产在线观看 | 欧美在线观看高清一二三区 | 免费精品精品国产欧美在线 | 国产亚洲精品看片在线观看 | 亚洲人和日本人jzz护士 | 成人午夜精品久久久久久久小说 | 国产在线视频精品视频免费看 | 四虎精品成人免费视频 | www.午夜精品| 久久在线免费观看视频 | 极品美女aⅴ高清在线观看 极品美女一级毛片 | 九九影院理论片私人影院 | 99999久爱视频在线观看 | 日日摸夜夜爽久久综合 | 久久免费视频一区 | 来自深渊在线观看 | 奇米影视777在线播放 | 日本一区二区高清 | 国产精品大全国产精品 | 999国产精品999久久久久久 | 国产91久久精品一区二区 | 天天躁夜夜躁很很躁麻豆 | 日日夜夜亚洲 | 97人人澡人人爽人人爱 | 97久久精品人人做人人爽 | 国产精久久一区二区三区 | 欧美一级毛片无遮 | 国产一区欧美二区 | 欧美成视频一theporn | 四虎国产成人亚洲精品 |