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;`↵
}↵
↵
`}`↵
``↵
``
↵
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;`↵
↵
``↵
``
