每日亿题之20220904

https://codeforc.es/problemset/problem/1716/D

今天两题，cf2000和2300(easy)/2500(hard)
D. Chip Move
给定n,k<=2e5,可以从位置0开始进行若干步的跳，第i步跳的长度为k+i的倍数，问跳到1,2,…,n位置的方案数%998244343
简单dp即可，因为忘了取模WA了一发

#include
using namespace std;
const int N=2e5+5,M=998244353;
int n,k,dp[N],sm[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=k;i<=n;i+=k) dp[i]=1,sm[i]=1;
    for(int kk=k+1,smn=k; smn+kk<=n; smn+=kk++)
    {
        for(int i=kk;i<=n;++i)
        {
            (dp[i]+=dp[i-kk])%=M;
        }
        for(int i=n;i;--i)
        {
            dp[i]= i>kk ? dp[i-kk] : 0;
            (sm[i]+=dp[i])%=M;
        }
    }
    for(int i=1;i<=n;++i) printf("%d ",sm[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

https://codeforc.es/problemset/problem/1712/E2

E2. LCM Sum (hard version)

You are given two positive integers l and r.
Count the number of distinct triplets of integers (i,j,k) such that l≤i 1≤t≤10^5
each test case contains two integers l and r (1≤l≤r≤2⋅105, l+2≤r).

因为lcm为k的倍数，所以仅lcmk，或{lcm2k&&((i,j,k)为(3,4,6)或(6,10,15)) }的情况不成立
lcm==k的情况，对于每个k，统计其>=L的因数个数sz_k，则sz_k(sz_k-1)/2为(i,j)pair的个数
正好sz*(sz-1)/2=0+1+2+…sz-1，所以可以对k从大到小的因数一次赋予权值0,1,2,…,sz-1，放在主席树上统计即可得到lcm==k的三元组个数之和
后面看别人的题解发现离线用树状数组就行了😫
还有这题开的空间真jb大，试了几次主席树开到N88都爆了，算了一下512MB能开到N160左右，好歹是过了

#include
using namespace std;
typedef long long LL;
const int N=2e5+5;
vector<int> dv[N];
int rt[N],lc[N*111],rc[N*111],cnt,nw;
LL sz[N*111];

void build(int &u,int v,int l,int r,int dl,int dr)
{
    u=++cnt;
    if(l==r) return (void)(sz[u]=sz[v]+dv[nw].size()-dl-1);
    int mi=l+r+1>>1;
    int dmi=lower_bound(dv[nw].begin()+dl,dv[nw].begin()+dr+1,mi)-dv[nw].begin();
    
    if(dl<dmi) build(lc[u],lc[v],l,mi-1,dl,dmi-1);
    else lc[u]=lc[v];
    if(dmi<=dr) build(rc[u],rc[v],mi,r,dmi,dr);
    else rc[u]=rc[v];
    sz[u]=sz[lc[u]]+sz[rc[u]];
}
LL query(int u,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return sz[u];
    int mi=l+r+1>>1;
    LL re=0;
    if(L<mi) re+=query(lc[u],l,mi-1,L,R);
    if(mi<=R) re+=query(rc[u],mi,r,L,R);
    return re;
}
int main()
{
    int T,L,R;
    for(int i=1;i<N;++i)
        for(int j=i*2;j<N;j+=i) dv[j].push_back(i);
    for(nw=2;nw<N;++nw) build(rt[nw],rt[nw-1],1,N-1,0,dv[nw].size()-1);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&L,&R);
        LL ans=1ll*(R-L+1)*(R-L)*(R-L-1)/6;
        ans-=query(rt[R],1,N-1,L,R);
        ans-=max(0,R/6-(L-1)/3);
        ans-=max(0,R/15-(L-1)/6);
        printf("%lld\n",ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

ILYL的no driver
20年的emo，很好听