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 — (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 — b]), f[b]); } `ll getH(int a, int b)` `{` ` return getC(a + b — 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;` `}` ``
