注意mod7654321用同余处理

这题就是菲波拉契数列的递推

啊亚，交错地方了

谁把这代码删了

哇卡卡 继续 矩阵矩阵

简单

非波拉七数列(我不知道fblq怎么写的)

so easy!

Fib~good

根据循环情况提取公式

#include <stdio.h>

int main()
{
int n, p = 1, h = 0, a = 0, g = 0;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int new_p = h, new_h = p + g, new_a = g, new_g = a + h;
p = new_p % 7654321;
h = new_h % 7654321;
a = new_a % 7654321;
g = new_g % 7654321;
}
printf("%d", (p + h + a + g) % 7654321);
}

DP
dp[i][j] 表示第i次考第j科的可能方案数

#include<cstdio>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

int n,dp[10001][4];  // 0 政治  1 历史  2 地理  3 综合
const int modx=7654321;

int main()
{
    read(n);
    dp[1][0]=1;
    for (register int i=2;i<=n;++i)
    {
        dp[i][0]=dp[i-1][1]%modx;
        dp[i][1]=(dp[i-1][0]+dp[i-1][2])%modx;
        dp[i][2]=(dp[i-1][3]+dp[i-1][1])%modx;
        dp[i][3]=dp[i-1][2]%modx;
    }
    printf("%d",(dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3])%modx);
    return 0;
}

博客分析地址
怎么化简的上面的链接里有，主要是将点分类讨论以及判断不会有重复情况出现

#include<iostream>
using namespace std;

int main()
{
    int a=1,b=1,n;
    cin>>n;
    if(n==1 or n==2)
    {
        cout<<1<<endl;
        return 0;
    }
    for(int i=3;i<=n;++i)
    {
        c=a+b;
        a=b%7654321;
        b=c%7654321;
    }
    cout<<c%7654321<<endl;
}

//斐波那契数列~不解释
#include<cstdio>
using namespace std;
const int st=7654321;
int a[3],n;
int main(){
    scanf("%d",&n);
    a[0]=1;
    a[1]=1;
    a[2]=2;
    for(int i=3;i<n;i++)
        a[i%3]=(a[(i-1)%3]+a[(i-2)%3])%st;
    printf("%d",a[(n-1)%3]);
    return 0;
} 

#include <iostream>
#include <cstring>
using namespace std;

int n;
int d[1000000];

int main(){
    cin >> n;
    memset(d,0,sizeof(d));
    d[0] = 0;
    d[1] = 1;   
    for(int i=2;i<=n;i++)
        d[i] = (d[i-1]%7654321 + d[i-2]%7654321);
    cout << d[n] % 7654321;
    return 0;
}

楼下能做到n = 10000000000000000000000000秒出么
```python
def work(a, b, c, d):
return a*a+b*c, a*b+b*d, c*a+c*d, c*b+d*d
def time_one(a, b, c, d):
return a+b, a, c+d, c
def quick_power(a, b, c, d, n):
if n == 1:
return a, b, c, d
a, b, c, d = quick_power(a, b, c, d, n/2)
a, b, c, d = work(a, b, c, d)
if n%2 == 1:
a, b, c, d = time_one(a, b, c, d)
return a%7654321, b%7654321, c%7654321, d%7654321
def main():
n = int(raw_input())
a, b, c, d = quick_power(1, 1, 1, 0, n)
print c

main()
```

#include <iostream>
using namespace std;

int main()
{
int n;
int a = 1;
int b = 1;
int total = 0;
cin >> n;
if( n <= 2 )
{
cout << "1";
}
else
{
for(int i=3;i<=n;i++)
{
total = a + b;
a = b;
b = total
}
cout <<total;
]

#include "stdio.h"
#include "memory.h"
#define MAXINT 7654321
int n;
int D[1000000];
int L[1000000];
int init(){
FILE *fpin = stdin;
fscanf( fpin, "%d", &n);
return 0;
}
int mdfs( int depth, char state){
if( depth == n-1) return 1; // Bug 1: ACL 1.
if( state == 'Z'){
return mdfs( depth+1, 'L')%MAXINT;
}else if( state == 'L'){
if( L[n-depth] == 0){
L[n-depth] = ( mdfs( depth+1, 'Z')+mdfs( depth+1, 'D'))%MAXINT;
}
return L[n-depth];
}else if( state == 'D'){
if( D[n-depth] == 0){
D[n-depth] = (mdfs( depth+1, 'L')+mdfs( depth+1, 'H'))%MAXINT;
}
return D[n-depth];
}else if( state == 'H'){
return mdfs( depth+1, 'D')%MAXINT;
}
}
int main(){
FILE *fpout = stdout;
init();
memset( D, 0, sizeof D);
memset( L, 0, sizeof L);
fprintf( fpout, "%d\n", mdfs( 0, 'Z'));
return 0;
}

简单递推
#include <cstdio>
#include <cstdlib>
#define mod 7654321

using namespace std;

int n;
int f[10005][5];

int main(int argc, const char *argv[]) {
scanf("%d", &n);
f[1][1] = 1;
for (int i = 2; i <= n; ++i) {
f[i][1] = f[i - 1][3] % mod;
f[i][2] = f[i - 1][4] % mod;
f[i][3] = (f[i - 1][1] + f[i - 1][4]) % mod;
f[i][4] = (f[i - 1][2] + f[i - 1][3]) % mod;
}
printf("%d\n", (f[n][1] + f[n][2] + f[n][3] + f[n][4]) % mod);
return 0;
}

#include <iostream>
#include <stdio.h>

using namespace std;

int fib(int n)
{
int sum = 0;
int prev = 1;
int dot;
for(int i = 1;i<=n;++i)
{
dot = sum%7654321 +prev;
prev = sum%7654321;
sum = dot;

}
return sum%7654321;
}
int main()
{
int n ;
cin>>n;
cout<<fib(n)<<endl;
return 0;
}

就是斐波那契数列
program p1093;
var a,b,c:int64;
i,n:integer;
begin
readln(n);
a:=1;
b:=1;
if n<3 then
begin
writeln('1');
exit;
end;
for i:=3 to n do
begin
c:=(a+b) mod 7654321;
a:=b;
b:=c;
end;
writeln(b);
end.

斐波那契数列~不解释
#include<cstdio>
using namespace std;
const int st=7654321;
int a[3],n;
int main(){
scanf("%d",&n);
a[0]=1;
a[1]=1;
a[2]=2;
for(int i=3;i<n;i++)
a[i%3]=(a[(i-1)%3]+a[(i-2)%3])%st;
printf("%d",a[(n-1)%3]);
return 0;
}

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;

if(n<3)
cout<<1;

else
{
int a=0;
int b=1;
int tot=0;
for(int i=1;i<=n-1;i++)
{

tot=(a+b)%7654321;
a=b;
b=tot;
}
cout<<tot;
}

return 0;
}