Brilliant Idea

One day, a brilliant idea came to Colin's mind.
Given a string $S$ with length $n$ (indexed from $0$ to $n-1$ ) consisting of lowercase letters.
Let $S_i$ denotes the character of $S$ with index $i$ , e.g. let $S=$ abc then $S_0=$ a and $S_1=$ b.
Let $S[l:r]$ denotes the substring of $S$ with index form $l$ to $r$ , e.g. let $S=$ abc then $S[1:2]=$ bc .

Now we play a game on the string. You want to take as many turns successfully as you can.

In one turn, you should:

first choose two integers $l,r$ satisfying $0\le l<r< n$ and $S[l:r]$ has at least two different characters (i.e. exist two different integers $x,y\in[l, r]$ satisfy $S_x\not =S_y$ ). If you cannot find such two integers $l,r$ , you fail in this turn, and the game ends.
then choose an integer $p\in[l,r]$ , change all the characters $S_i\ (i\in[l, r])$ into $S_p$ ; then you take this turn successfully.

For example, let $S=$ abc and choose $l=1,r=2,p=2$ , then after this turn, $S$ becomes acc .
Colin wants to ask you, at most how many turns can be successfully taken on string $S$ ?

Eva thought that's too easy for you, so she upgraded this problem to a counting problem. Let $ans_S$ denotes the answer to the above question for string $S$ , you need to count that among all strings with length $n$ consisting of lowercase letters:
1. how many strings satisfy $ans_S=0$ ?
2. how many strings satisfy $ans_S>0$ and $ans_s$ is finite?
3. how many strings satisfy $ans_S$ is infinite?

A single line contains three integers.
The first one represents the number of strings satisfying $ans_S=0$ , module $10^9+7$ .
The second one represents the number of strings satisfying $ans_S>0$ and $ans_s$ is finite, module $10^9+7$ .
The third one represents the number of strings satisfying $ans_s$ is infinite, module $10^9+7$ .

#include <iostream> using namespace std; long long a,b,c=26,sum=1,mod=1e9+7; int main() { cin>>a; if(a==2) cout<<"26 650 0"; else{ b=a%mod; while(b>0){ if(b&1) sum=(sum*c)%mod; c=(c*c)%mod; b>>=1; } cout<<"26 0 "<<(sum-26+mod)%mod; } return 0; }

#include <iostream> using namespace std; long a,b,c=26l,sum=1,mod=1e9+7; int main() { cin>>a; if(a==2) cout<<"26 650 0"; else{ b=a%mod; while(b>0){ if(b&1) sum=(sum*c)%mod; c=(c*c)%mod; b>>=1; } cout<<"26 0 "<<(sum-26+mod)%mod; } return 0; }

详情