首页 > 代码库 > zoj 3538 Arrange the Schedule
zoj 3538 Arrange the Schedule
In Summer 2011, the ZJU-ICPC Team has a n-days training schedule. ZJU-ICPC Team has been divided into 4 Group: Akiba, BiliBili, CIA, Double(Group A, B, C, D). There is a group in charge of the training problems on each day. As the ICPC Team manager, you have to decide which team is in charge of the problems on each day. But there are something you should rememeber:
1. No team is able to provide problems on two adjacent days.
2. There are m days in the Summer 2011 that which group is in charge of the problems have been decided. (e.g. Akiba provides problems on day 1, BiliBili provides problems on day 6. And these can not be changed)
How many ways are there to arrange the schedule? Output the answer modulo 1000000007.
Input
There are multiple test cases(less than 50). Each case contains two integers n, m (1 ≤ n ≤ 10000000, 0 ≤ m ≤ 10), which indicate the number of days in Summer 2011 and the number of days that have been decided.
Following m lines. Each line contains one integer ai and one upper letter Ch (‘A‘ ≤ Ch ≤ ‘D‘), indicate that on day ai (1 ≤ ai ≤ n), group Ch is in charge of the problems. We guarantee that all ai are distinct. There is a blank line after each input case.
Output
For each case, output a single line containing the answer, the number of the ways to arrange the schedule modulo 1000000007.
Sample Input
3 2 1 A 3 C 2 1 1 D
Sample Output
2 3
Hint
Case 1: 2 ways: ABC, ADC. Case 2: 3 ways: DA, DB, DC.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define p 1000000007
using namespace std;
struct mat
{
long long t[2][2];
void set()
{
memset(t,0,sizeof(t));
}
} a,b;
mat multiple(mat a,mat b)
{
int i,j,k;
mat temp;
temp.set();
for(i=0; i<2; i++)
for(j=0; j<2; j++)
{
for(k=0; k<2; k++)
temp.t[i][j]=(temp.t[i][j]+a.t[i][k]*b.t[k][j])%p;
}
return temp;
}
mat quick_mod(mat b,int m)
{
mat t;
t.set();
for(int i=0; i<2; i++) t.t[i][i]=1;
while(m)
{
if(m&1)
{
t=multiple(t,b);
}
m>>=1;
b=multiple(b,b);
}
return t;
}
long long quick_Mod(int m)
{
long long t=1;
long long b=3;
while(m)
{
if(m&1) t=t*b%p;
m>>=1;
b=b*b%p;
}
return t;
}
long long solve(int m,int c)
{
if(m<=0) return 1;
b.t[0][0]=0;
b.t[0][1]=1;
b.t[1][0]=3;
b.t[1][1]=2;
a=quick_mod(b,m-1);
if(c==1) return 3*a.t[0][0]+2*a.t[1][0];
return 3*a.t[0][1]+2*a.t[1][1];
}
struct node
{
int q;
char s[3];
}t[12];
bool cmp(node a,node b)
{
return a.q<b.q;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int sum1=0,sum2=0;
long long ans=1;
if(m==0)
{
printf("%lld\n",quick_Mod(n-1)*4%p);
continue;
}
for(int i=0;i<m;i++)
{
scanf("%d%s",&t[i].q,t[i].s);
}
sort(t,t+m,cmp);
ans=ans*quick_Mod(t[0].q-1)%p;
ans=ans*quick_Mod(n-t[m-1].q)%p;
for(int i=0;i<m-1;i++)
{
if(t[i].s[0]==t[i+1].s[0])
{
sum1=t[i+1].q-t[i].q-1;
if(sum1==0)
{
ans=0;
break;
}
else
ans=ans*solve(sum1,1)%p;
}
else sum2=t[i+1].q-t[i].q-1,ans=ans*solve(sum2,0)%p;
}
printf("%lld\n",ans);
}
return 0;
}