D - Infinite Path

题意：给定n个点,a数组，b数组.a[i]表示点 i - > 点a[i] 有一条有向边,b[i]表示边的颜色.
定义：p^1=[ a[1],a[2],a[3]...a[n] ],p^2=[ a[a[1]],a[a[2]],....,a[a[n]] ],p^k 如例子一样迭代k次.求p最小长度满足p集合内点成一个环并且颜色相同.( a数组的元素是1~n的全排列 ) (n<=1e5 )
分析:可以从a数组元素得知，图最终是某m个不相交的环(简单证明可得)，那么我们只需要枚举所有的环，然后假设第i个环的长度是k,根据迭代关系，我们只要枚举k的因子进行check颜色更新答案即可.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    int t;
    cin>>t;
    while( t-- )
    {
        int n;cin>>n;
        vector<int>g(n),c(n),v(n);   // v(i) i是否加入环中 
        for( auto &i:g ) cin>>i,i--; // g(i) 下一位置 
        for( auto &i:c ) cin>>i;     // c(i) 颜色 
        int ans=n+1;
        for( int i=0;i<n;i++ )
        {
            if( v[i] ) continue;
            vector<int> cc;         // 存环上的点 
            while( !v[i] ) 
            {
                cc.push_back(c[i]);
                v[i]=1;
                i=g[i];
            }                         // 最终 i一定会回环起点 
            int l=cc.size();     
            for( int i=1;i<=l;i++ )
            {
                if( l%i ) continue;
                for( int s=0;s<i;s++ )
                {
                    int y=1;
                    for( int j=s;j<l;j+=i )    
                    {
                        if( cc[s]!=cc[j] ) y=0;
                    }
                    if( y && i<ans ) ans=i;
                }
            }
        }
        cout<<ans<<endl;
    } 
} 

E - Count The Blocks

题意:定义一个数字n，该数字十进制下连续长度为1 ~ len(n)的数字贡献，现在求[1,10^n-1]，连续长度为1~len(n)的数字贡献和是多少.答案要模998244353.举个例子:00033440.长度为3的有1个000，长度为2 的有两个33和44，长度为1的有1个0.(n<=10^100000)
分析:

• 枚举当前这位开始向后连续i个相同数字的方案数.
• i=n时，ans=10.否则分两种情况，一种是连续i个相同数字的起始位置在最左端或者最终位置在最右端,第二种情况在中间位置----这种起始位置有(n-i-1)个.对应情况算答案即可.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=998244353;
const int maxn=2e5+10;
ll p[maxn];
ll ans[maxn];
int main()
{
    p[0]=1;
    for( int i=1;i<maxn;i++ ) p[i]=(p[i-1]*10)%mod;
    ll n;
    cin>>n;
    for( int i=1;i<=n;i++ )
    {
        if( i==n ) ans[i]=10;
        else
        {
            ans[i]+=p[n-i]*9*2;
            ans[i]+=(n-i-1)*9*9*p[n-i-1];
            ans[i]%=mod;
        }
    } 
    for( int i=1;i<=n;i++ ) cout<<ans[i]<<" ";
} 

F - AND Segments

题意：给定m个(l,r,x)条件，请构造序列长度为n的数组,满足所有条件[li,ri]的区间所有元素的按位&等于xi,并且序列元素大小 小于2^k.( 1<=l,r<=n<=5e5，k<=30,xi<2^k )
**分析：

• 首先了解按位&的性质.对于[l,r]二进制第i位按位&为0,只要[l,r]内元素有一个0那么便满足条件,如果第i位按位&为1，那么对应所有元素必须为1.
• 那么考虑按二进制位分情况讨论.枚举二进制位，对于当前位 所有条件区间进行建差分数组.使用动态规划dp[i]---最后一个0正好位于位置i，并且它左边的所有0段至少包含一个0.我们只要预处理出当前i为0段区间右端的最大左端点值.然后维护一个前缀和更新即可.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=998244353;
const int maxn=5e5+10;

int n,m,k;
int l[maxn],r[maxn],a[maxn],b[maxn];

int cl[maxn],dif[maxn];
ll f[maxn],psum[maxn];

ll solve()
{
    for( int i=1;i<=n;i++ ) dif[i]=0,cl[i]=-1;
    for( int i=1;i<=m;i++ )
    {
        if( b[i] ) ++dif[l[i]],--dif[r[i]+1];  // 差分 
        else cl[r[i]]=max(cl[r[i]],l[i]);       // 限制区间 0段区间 
    }

    int leftmost=0;
    f[0]=psum[0]=1;
    for( int i=1;i<=n;i++ )   // f(i) 最后一个0正好位于位置 i，并且它左边的所有0段至少包含一个 0
    {
        dif[i]+=dif[i-1];
        if( dif[i] ) f[i]=0;
        else
        {
            f[i]=psum[i-1];
            if( leftmost ) f[i]=( f[i]-psum[leftmost-1]+mod )%mod;
        }
        psum[i]=(f[i]+psum[i-1])%mod;
        leftmost=max(leftmost,cl[i]);
    }
    ll res=0;
    for( int i=leftmost;i<=n;i++ ) res=(res+f[i])%mod;
    return res;
}

int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for( int i=1;i<=m;i++ ) scanf("%d%d%d",&l[i],&r[i],&a[i]);
    ll ans=1;
    for( int i=0;i<k;i++ ) // 对每一个二进制位枚举 
    {
        for( int j=1;j<=m;j++ ) b[j]=a[j]>>i & 1; // m条件限制 存于 b[] 
        ans=ans*solve()%mod;
    }
    printf("%lld\n",ans);
    return 0;
}