Can someone help me find a counterexample on Atcoder beginner problem F?

Правка en2, от Wonsei, 2020-06-21 17:56:09

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)