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) = 25^(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),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) = 25^(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),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;↵
}↵
~~~~~↵
↵
