Can someone help me find a counterexample on Atcoder beginner problem F?
Разница между en2 и en3, 208 символ(ов) изменены
Problem : https://atcoder.jp/contests/abc171/tasks/abc171_f↵

Ill explain my idea below with the first example.↵

_______ o ___________ o ________ f __________↵

we are able to place letters in the 4 slots here.↵

Lets say that we place ↵
a letters on the first slot, b letters on the second,↵
c letters on the third, and d letters on the fourth slot.↵
therefore, a+b+c+d = n.↵

The first slot is free to place slot -> we have 26^a ways to put it.↵

The second slot, third slot, fourth slots have a restriction;↵
you cannot place the letter that is at the left of the slot.↵
(you can't place o in the second, third slot, you can't place f in the fourth slot)↵
-> by this restriction, we can prevent duplicates being counted.↵
-> ex) ooaoaaof -> this will be only counted one time.↵
-> therefore, there's 25^(b+c+d) = 26^(n-a) ways to put in the slots.↵

if a is 0, b+c+d = n.↵
the ways to distribute numbers to b, c, d is H(3,n)=C(3+n-1, n).↵

if a is 1, b+c+d = n-1.↵
the ways to distribute numbers to b, c, d is H(3,n-1)=C(3+n-1-1, n-1)↵

...↵

if a is n, b+c+d = 0↵
the ways to distribute numbers to b, c, d is H(3,0)=C(3+0-1, 0).↵

--↵
therefore the total = sigma k=0 to n (26^k * 25^n-k * H(len(S)-1,n-k))↵

there was my logic, and I coded it but it came with a result of only 70 out of 100.↵

Can someone help me finding the counterexample?↵

Code below:↵
`
~~~~~↵
#include <iostream>`
`#include <vector>`
`#include <cmath>`
`#include <algorithm>`
`#include <climits>`
`#include <set>`
`#include <map>`
`#include <queue>`
`#include <deque>`
`#include <stack>`
`#include <string>`
`#include <list>`
`#include <ctime>`
`#include <complex>`
`#include <bitset>`
`#include <tuple>`
``
`#define ff first`
`#define ss second`
`#define MOD 1000000007LL`
``
`using namespace std;`
`using pii = pair<int, int>;`
`using ll = long long;`
``
`vector<ll> f(3000000);`
``
`tuple<ll, ll, ll> exgcd(ll a, ll b) {`
`    if (b == 0)`
`        return make_tuple(a, 1, 0);`
`    ll g, x, y;`
`    tie(g, x, y) = exgcd(b, a % b);`
`    return make_tuple(g, y, x &mdash;- (a / b) * y);`
`}`↵
``
}↵

`ll moddiv(ll a, ll b)`
`{`{
`    ll bb;`
`    tie(ignore, bb, ignore) = exgcd(b, MOD);`
`    if (bb < 0) b += MOD;`
`    return (a * bb) % MOD;`
`}`↵
``
}↵

`ll getC(int a, int b)`
`{`{
`    if (a < b) return 0;`
`    return moddiv(moddiv(f[a], f[a &mdash;- b]), f[b]);`
`}`↵
``
}↵

`ll getH(int a, int b)`
`{`{
`    return getC(a + b &mdash;- 1, b);`
`}`↵
``
}↵

`int main()`
`{`{
`    ios::sync_with_stdio(false);`
`    cin.tie(0);`
``
`    f[0] = 1;`
`    for (int i = 1; i < f.size(); i++) f[i] = (f[i - 1] * i) % MOD;`
``
`    int k;`
`    cin >> k;`
`    string s;`
`    cin >> s;`
`    ll answer = 0;`
`    vector<ll> p26(k + 1), p25(k + 1);`
`    p26[0] = p25[0] = 1;`
`    for (int i = 1; i <= k; i++) {`
`        p26[i] = (p26[i - 1] * 26) % MOD;`
`        p25[i] = (p25[i - 1] * 25) % MOD;`
`    }`
`    for (int i = 0; i <= k; i++) {`
`        ll tmp = (p26[i] * getH(s.length(), k - i)) % MOD;`
`        tmp = (tmp * p25[k - i]) % MOD;`
`        answer = (answer + tmp) % MOD;`
`    }`
`    cout << answer;`
``
`    return 0;`
`}`↵
``↵
``
}↵
~~~~~↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Wonsei 2020-06-21 18:45:27 8
en5 Английский Wonsei 2020-06-21 18:03:30 2 Tiny change: 'b+c+d) = 26^(n-a) way' -> 'b+c+d) = 25^(n-a) way'
en4 Английский Wonsei 2020-06-21 18:01:56 2 Tiny change: '* H(len(S)-1,n-k))\n\n' -> '* H(len(S),n-k))\n\n'
en3 Английский Wonsei 2020-06-21 17:58:22 208
en2 Английский Wonsei 2020-06-21 17:56:09 168
en1 Английский Wonsei 2020-06-21 17:55:09 3102 Initial revision (published)