HDU 2065 红色病毒难题

这是一道数学题，使用高中的排列组合公式即可求解。题中说输出%100后的值，那么答案一定存在循环。

解法：分类讨论：

现在有 $i$ 个位置

①A,C均不出现，只填B,D 情况有 $2^n$ 种

②A,C只出现其中1个，情况有 $C_i^2 2^{i-2}+C_i^4 2^{i-4}+......+C_i^k 2^{i-k}(k\in \{2,4,6\}\text{...}\},i>=k)$

③A,C均出现，应该给A,C 4个以上的偶数个空间(用 $k$ 表示偶数空间数量， $a$ 表示填A的数量)。情况有

$\sum _{k=4}^i (2^{i-k} C_i^k \sum _{a=2}^k C_k^a)$ $其中k\in \{4,6,8\text{...}\},a\in \{2,4,6\text{...}\},k<i,a<k$

因为python支持高精度，先写成python,算出每个数对应的 $ans[i]$

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 29 16:01:05 2020

@author: nameETC
"""

C = [[0 for i in range(101)] for j in range(101)]
'''递推求组合数'''
C[1][1]=1;C[1][0]=1;
for i in range(2,101):
    C[i][0]=1;
    for j in range(1,i+1):
        C[i][j]=C[i-1][j]+C[i-1][j-1];

ans = [0 for i in range(101)];
ans[1]=2;
for i in range(2,101):
    ans[i]+=2**i; '''A,C均未出现'''

    k=2;temp=0;'''A,C出现其一'''
    while k<=i:
        temp+=C[i][k]*(2**(i-k))
        k+=2;
    ans[i]+=temp*2;

    k=4;temp=0;'''A,C均出现'''
    while k<=i :
        for kk in range(2,k,2):
            temp+=C[i][k]*C[k][kk]*(2**(i-k));

        k+=2;
    ans[i]+=temp;
print("ans[]={",end="");
for i in range(0,50):
    if i<49:
        print("%d,"%(ans[i]%100),end="");
    else:
        print("%d};"%(ans[i]%100));

发现ans的循环规律。
写成C++程序

#include<cstdio>

int ans[]={0,2,6,20,72,72,56,60,12,92,56,0,52,12,56,40,92,32,56,80,32,52,56,20};

int main(){
    int T;
    while(scanf("%d",&T)==1&&T){
        int kase=0;
        while(kase<T){
            long long x;scanf("%lld",&x);
            if(x<=4){
                printf("Case %d: %d\n",++kase,ans[x]);
            }
            else printf("Case %d: %d\n",++kase,ans[(x-4)%20+4]);
        }
        printf("\n");
    }
    return 0;
}