话说T3都把式子推出来了结果忘记差分约束怎么写了。

光线(light)

题面：有\(n\)个玻璃板，第\(i\)个玻璃板的透光率为\(a_i\%\)，反射率为\(b_i\%\)，有大小为\(1\)个单位的一束光从第\(1\)个玻璃板开始，有多少光能穿透\(n\)层玻璃板。
题解：考虑\(n=2\)时，可以简单算出两个玻璃板组合后的反射率和透光率。将\(n\)个玻璃板依次组合起来，就可以算出整体的透光率。
复杂度\(\Theta(n\log p)\)
代码：

#include<cstdio>
#define int long long
const int N=500005,mod=1000000007;
int n,i100,a[N],b[N],ans=1;
inline int mul(int x,int y){return x*y%mod;}
inline void Mul(int&x,int y){x=mul(x,y);}
inline int pow(int x,int y){
    int res=1;
    for(;y;Mul(x,x),y>>=1)if(y&1)Mul(res,x);
    return res;
}
inline int inv(int x){return pow(x,mod-2);}
inline int div(int x,int y){return mul(x,inv(y));}
inline void Sub(int&x,int y){if((x-=y)<0)x+=mod;}
inline int sub(int x,int y){return Sub(x,y),x;}
inline void Add(int&x,int y){if((x+=y)>=mod)x-=mod;}
inline int add(int x,int y){return Add(x,y),x;}
signed main(){
    freopen("light.in","r",stdin),freopen("light.out","w",stdout),scanf("%lld",&n),i100=inv(100);
    for(int i=1;i<=n;i++)scanf("%lld%lld",a+i,b+i),Mul(a[i],i100),Mul(b[i],i100);
    for(int i=1;i<=n;i++){
        if(i^1)Add(b[i],div(mul(pow(a[i],2),b[i-1]),sub(1,mul(b[i-1],b[i]))));
        if(i^n)Mul(ans,div(a[i],sub(1,mul(b[i],b[i+1]))));
        else Mul(ans,a[i]);
    }
    return printf("%lld\n",ans),fflush(stdout),fclose(stdin),fclose(stdout),0;
}

逼死强迫症(mad)

题面：有\(2\times n\)的网格，两个\(1\times 1\)的矩形和无限个\(2\times 1\)的矩形，要填满所有网格，且两个\(1\times 1\)的矩形不能相邻，求方案数。
题解：定义\(f(i,0)表示\)前\(i-1\)列填满，用了\(0\)个\(1\times 1\)的矩形，第\(i\)列填了\(0\)个的方案数。
\(f(i,1)表示\)前\(i-1\)列填满，用了\(2\)个\(1\times 1\)的矩形，第\(i\)列填了\(0\)个的方案数。
\(f(i,0)表示\)前\(i-1\)列填满，用了\(1\)个\(1\times 1\)的矩形，第\(i\)列填了\(1\)个的方案数。
状态转移方程
\(f(i,0)=f(i-1,0)+f(i-2,0)\)
\(f(i,1)=f(i-1,1)+f(i-2,1)+f(i-1,2)-f(i-1,0)\)
\(f(i,2)=2(f(i-1,0)+f(i-2,0))+f(i-1,2)\)
最后答案为\(f(n+1,2)-nf(n+1,0)\)
矩阵快速幂优化即可。
令矩阵大小\(a=5\)，时间复杂度\(\Theta(a^3T\log n)\)
代码：

#include<cstdio>
#include<cstring>
#define int long long
const int mod=1000000007;
int T,n,f[5],a[5][5],g[5],b[5][5],m;
inline int mul(int x,int y){return x*y%mod;}
inline void Add(int&x,int y){if((x+=y)>=mod)x-=mod;}
inline void Sub(int&x,int y){if((x-=y)<0)x+=mod;}
inline int sub(int x,int y){return Sub(x,y),x;}
signed main(){
    for(freopen("mad.in","r",stdin),freopen("mad.out","w",stdout),scanf("%lld",&T);T--;){
        scanf("%lld",&n),f[0]=1,f[1]=1,f[2]=4,f[3]=1,f[4]=0,a[0][0]=1,a[0][1]=0,a[0][2]=0,a[0][3]=1,a[0][4]=0,a[1][0]=-1,a[1][1]=1,a[1][2]=1,a[1][3]=0,a[1][4]=1,a[2][0]=2,a[2][1]=0,a[2][2]=1,a[2][3]=2,a[2][4]=0,a[3][0]=1,a[3][1]=0,a[3][2]=0,a[3][3]=0,a[3][4]=0,a[4][0]=0,a[4][1]=1,a[4][2]=0,a[4][3]=0,a[4][4]=0,m=n-1;
        for(;m;m>>=1){
            if(m&1){
                memset(g,0,sizeof(g));
                for(int i=0;i<5;i++)for(int j=0;j<5;j++)Add(g[i],mul(a[i][j],f[j]));
                memcpy(f,g,sizeof(g));
            }
            memset(b,0,sizeof(b));
            for(int i=0;i<5;i++)for(int k=0;k<5;k++)for(int j=0;j<5;j++)Add(b[i][j],mul(a[i][k],a[k][j]));
            memcpy(a,b,sizeof(b));
        }
        printf("%lld\n",sub(f[1],mul(f[0],n)));
    }
    return fflush(stdout),fclose(stdin),fclose(stdout),0;
}

节日(fes)

题面：有\(n\)个数\(a_1\dots a_n\)，\(m_1\)个限制关系1，\(m_2\)个限制关系2，限制关系1唯一个二元有序对\((i,j)\)表示\(a_i=a_j+1\)，限制关系2唯一个二元有序对\((i,j)\)表示\(a_i\ge a_j\)，求\(a\)在去重后有多少个数。
题解：差分约束，对于限制关系1建立\((i,j)\)边权为\(-1\)的边和\((j,i)\)边权为\(1\)的边。
对于限制关系2建立\((j,i)\)的边。
对于图中的一个强连通分量表示一个明确的限制关系，可以出现的数的种类为最长路\(+1\)。
先用tarjan算法求出强联通分量，再在每个强联通分量内部用floyd算法求出最长路即可。
代码：懒得写

子序列(subsequence)

题面：长度为\(n\)的序列\(a\)，可以选择一个长度为\(k(1\le k\le n)\)的序列\(id\)，使得\(a_{id_j}\leftarrow \sum_{1\le k\le j}a_{id_k}\)，问进行一次操作后，\(a\)有多少种不同的情况。
题解：只有在前缀和为\(0\)时，情况才会重复。
令\(f(i,j)\)表示将\(a_i\leftarrow a_i+j\)时的方法数。
若\(a_i+j\neq 0\)，那么将\(i+1\le k\le n\)进行更新。
\(f(i,j)\stackrel\sum{\longrightarrow}f(k,a_i+j)\)
若\(a_i+j=0\)，那么将\(i+1\le k\le n\)进行更新时，\(a_k\leftarrow a_k+v\)，\(v\in\{a_x|i+1\le x\le k-1\}\)
\(f(i,j)\stackrel\sum{\longrightarrow}f(k,v)\)
时间复杂度\(\Theta(n^3\log n|A|)\)，A为值域。
代码：

#include<cstdio>
#include<set>
const int N=105,mod=1000000007;
int n,a[N],d[N][2010],*f[N],ans=1;
std::set<int>s;
inline void Add(int&x,int y){(x+=y)>=mod&&(x-=mod);}
int main(){
    freopen("subsequence.in","r",stdin),freopen("subsequence.out","w",stdout),scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=0;i<=n;i++)f[i]=d[i]+1005;
    f[0][0]=1;
    for(int i=0;i<n;i++)for(int j=-1000;j<=1000;j++){
        if(!f[i][j])continue;
        s.clear();
        if(a[i]+j)s.insert(a[i]+j);
        for(int k=i+1;k<=n;k++){
            for(int x:s)Add(f[k][x],f[i][j]);
            if(a[i]+j==0&&a[k])s.insert(a[k]);
        }
    }
    for(int i=1;i<=n;i++)for(int j=-1000;j<=1000;j++)Add(ans,f[i][j]);
    return printf("%d\n",ans),fflush(stdout),fclose(stdin),fclose(stdout),0;
}