topcoder[SRM 377]外星语言_综合

【题目描述】

一个国际科研小组昨天发现了一张奇奇怪怪的纸片。他们相信它大约有一百万年的历史。而且，它包含了一些用外星语言写下的文本。下面是对于这种外星语言的所有已知事实：
1. 外星语言的字母表由P个元音和Q个辅音构成。
2. 外星语言的每个单词包含了至多N个元音和至多N个辅音。
3. 在单词中元音总是在辅音之前，即每个单词由一段辅音和后面紧跟着的一段元音构成。
元音或辅音的个数都可以是零。
4. 每个单词至少包含一个字母。
5. 每个单词都可以有重音。外星人将重音标记在字母而非音节上。有三种可能的情况：单词没有重音，单词由一个重音（它可以在任一个字母上），单词有两个重音（一个在元音字母上，一个在辅音字母上）。
6. 两个字母拼写完全相同，但重音不同的单词是不同的。
科学家们希望知道外星语言中单词的总数。他们把这个任务作为练习留给了你。
你的程序被要求返回外星语言中单词的总数模M的值。
【输入格式】

一行，有四个整数：P，Q，N，M
【输出格式】

一行，一个整数：外星语言的单词总数模M的值
【样例输入】

sample1:
1 1 1 9

sample2:
2 3 2 1000

sample3:
1 1 1000000000 1000000000

sample4:
123 456 789 987654321
【样例输出】

sample1:
8

sample2:
577

sample3:
0

sample4:
345494202
【提示】

1<=N,P,Q<=10^9
1<=M<=10^9
【来源】

TopCoder Algorithm SRM 377, Div 1, 1000

题解：

可以看出元音和辅音是相对独立的,可以分别计算再乘法原理
令f[i]为选i个元音的方案,f1[i]为无重音方案,f2[i]为有重音方案
g[i]为f[i]的前缀和
那么有

g [i] = g [i ? 1] + f [i]

$g[i]=g[i-1]+f[i]$

f [i] = f 1 [i] + f 2 [i]

$f[i]=f1[i]+f2[i]$

f 1 [i] = f 1 [i ? 1] ? P

$f1[i]=f1[i-1]*P$

f 2 [i] = f 1 [i] ? i

$f2[i]=f1[i]*i$
数据范围比较大,考虑构造矩阵
| 1 1 0 0 | | g[i-1] | | g[i] |
| 0 0 2P P | | f[i] | = | f[i+1] |
| 0 0 P 0 | | f1[i] | | f1[i+1] |
| 0 0 P 0 | | f2[i] | | f2[i+1] |
正确性？

f [i + 1] = f 1 [i + 1] + f 2 [i + 1]

$f[i+1]=f1[i+1]+f2[i+1]$

= f 1 [i] ? P + f 1 [i + 1] ? (i + 1)

$=f1[i]*P+f1[i+1]*(i+1)$

= f 1 [i] ? P + f 1 [i] ? P ? (i + 1)

$=f1[i]*P+f1[i]*P*(i+1)$

= f 1 [i] ? P + f 1 [i] ? P ? i + f 1 [i] ? P

$=f1[i]*P+f1[i]*P*i+f1[i]*P$

= f 1 [i] ? 2 P + f 2 [i] ? P

$=f1[i]*2P+f2[i]*P$
辅音构造类似
时间复杂度O(logn)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int mod;
struct matrix{long long a[5][5];int I,J;matrix(){memset(a,0,sizeof(a));I=J=0;}matrix operator *(const matrix &b)const{matrix c;for(int i=1;i<=I;i++)for(int j=1;j<=b.J;j++)for(int k=1;k<=J;k++){c.a[i][j]+=a[i][k]*b.a[k][j];c.a[i][j]%=mod;}c.I=I,c.J=b.J;return c;}
};
matrix f1,f2;
matrix t1,t2;
matrix d1,d2;
matrix qpow1(int x){if(x==1)return f1;matrix tmp=qpow1(x/2);tmp=tmp*tmp;if(x&1)tmp=tmp*f1;return tmp;
}
matrix qpow2(int x){if(x==1)return f2;matrix tmp=qpow2(x/2);tmp=tmp*tmp;if(x&1)tmp=tmp*f2;return tmp;
}
int main(){freopen("alienlanguage.in","r",stdin);freopen("alienlanguage.out","w",stdout);int p,q,n;scanf("%d %d %d %d",&p,&q,&n,&mod);f1.I=f1.J=4;f2.I=f2.J=4;f1.a[1][1]=f1.a[1][2]=f2.a[1][1]=f2.a[1][2]=1;f1.a[2][4]=f1.a[3][3]=f1.a[4][3]=f1.a[4][4]=p;f1.a[2][3]=2*p;f2.a[2][4]=f2.a[3][3]=f2.a[4][3]=f2.a[4][4]=q;f2.a[2][3]=2*q;t1.I=t2.I=4;t1.J=t2.J=1;t1.a[1][1]=0;t1.a[2][1]=2*p;t1.a[3][1]=p;t1.a[4][1]=p;t2.a[1][1]=0;t2.a[2][1]=2*q;t2.a[3][1]=q;t2.a[4][1]=q;d1=qpow1(n);d2=qpow2(n);d1=d1*t1;d2=d2*t2;long long ans=(((d1.a[1][1]*d2.a[1][1])%mod+d1.a[1][1])%mod+d2.a[1][1])%mod;printf("%lld\n",ans);
return 0;
}